更新路径中最重边时计算最短路径的算法

Question

对于给定图G =（V，E）和路径p = v1-> v2-> ...-> vk

w *（p）表示v1和vk之间的路径的权重，但不包括max_edge。

对于V中的给定顶点s

[我想找到一种算法，该算法使用Dijkstra计算s与G中的每个v之间的值w *（p）的最短路径。

我猜，我应该先更改原始图G。也许将一条边复制为值（-1 * max edge）..或将最重的边设为零

我不确定，所以将不胜感激。

谢谢你。

Answer 1

您可以进行修改的Dijkstra算法，其中将每个顶点添加两次，一次添加法线路径权重，第二次添加最重边缘的权重（记住每个顶点最重边缘的权重）。在更新阶段，应考虑顶点的类型，邻居的类型，边缘权重和迄今为止最重的边缘。