graph - 找到可能忽略 1（最长）边的最短路径

Question

我想知道是否可以通过这种方式修改 Dijkstra'a 算法：假设两个顶点之间有 2 条路径，长度如下：

5, 8, 6, 9  // sum=28
2, 4, 8, 25 //sum=39

第一条路径较短，但在忽略两者中最长的边之后，我得到以下总和：19 和 14，所以我选择了第二条路径。

也许有不同的方法来解决它，而不使用 Dijkstra？

Answer 1

我不确定这个想法是否有效，但首先在我看来它可以。

对于每个访问过的节点，除了距离之外D(n)，存储路径上最长边的长度，例如L(v)。min D(n) + L(n) - max(L(n), weight(v,n))对于所有已访问的邻居，未访问的相邻节点的距离为n。L(v)的下一个访问节点是max(L(n), weight(v,n))，如果n是到 的路径上的最后一个节点v。如果有更多相同长度的v（更多n's）路径，则选择最大的路径L(v)。