负重Dijkstra

Question

我试图找到一个负权图(没有负循环)的有向图的例子，这样在它上运行dijksra将为所有图中的顶点(源节点除外)产生错误的结果。

在dijkstra产生的一些结果是错误的情况下，不难找到一个图的例子。但是我找不到上面描述的图表的例子，有人能帮我吗？

谢谢。

Answer 1

假设图G有三个节点A、B和C，三个弧(A，B,5)，(A，C,2)，(B，c，-10)，源是A。

现在从A到C的最短路径是2，这是错误的。

应该是-5。