如果唯一的负边缘成本来自初始节点呢？这个算法还能用吗？
我觉得是的，因为我想不出反例，但我很难证明。有反例吗？
对于dijkstra来说，负边是一个问题，因为如果有一条可以稍后选择的边的权重很大，则无法保证您选择的边会产生最短的路径。但是如果只有负边从初始节点出来，我看不出问题。
我不是在找算法。我在找一些关于狄克斯特拉的见解。
我说的是有向图，如果有区别的话。
最佳答案
反例：
图g=（v，e），顶点v={a，b}，边e={（a，b），（b，a）}，权函数w（a，b）=-2，w（b，a）=+1。
有一个负权重循环，因此最小距离未定义（即使使用作为初始节点）。