具有一条负边的最短路径

您的方法不起作用的原因是它不公平地惩罚具有更多边的路径。

假设从源节点到目标节点有两条路径,一条具有更多边,但权重较低,另一条具有较少边且权重较高。假设每个边上的权重是3。

原始路径:

S -> 1 -> 1 -> 1 -> 1 -> 1 -> T    wt = 5
S -> 4 -> 3 -> T                   wt = 7

添加权重后的路径:

S -> 4 -> 4 -> 4 -> 4 -> 4 -> T    wt = 20
S -> 7 -> 6 -> T                   wt = 13

如您所见,第二条路径现在被错误地标识为较短的路径。