Dijkstra在哪些情况下适用于负权重

Question

Dijkstra不能保证处理具有负权重的图：为什么不；t Dijkstra'；s算法适用于负权重边？，但我能假设它适用于以下情况之一吗(即使是负权重(

1. 没有有向环的有向图

2. 有向图，其基础结构图是树(已连接且没有循环(

注意：我所说的基础结构图是指去除所有边的方向时的同一个图。

Answer 1

对于1。你可以通过搜索找到许多反例，其中一些在问答中给出；你链接到的A。

对于2.，如果图的无向版本是一棵树，那么任何两个节点之间都不能有一条以上的路径。因此，无论Dijkstra的算法找到什么路径，默认情况下都是最短的。我将让你来证明Dijkstra的算法确实找到了一条路径(如果存在的话(。