Single Source shortest Path
Dijkstra的-有向和无向-只适用于正边权循环？是吗？
贝尔曼福特-不存在任何周期
All source shortest path
Floyd Warshall-无信息
Minimum Spanning Tree
（没有关于边权重或图形或循环性质的信息）
克鲁斯卡尔的
普里姆-无向
巴鲁卡的
最佳答案
我不知道问题是什么，但这里…
Dijkstra算法的经典实现只能处理正边缘权值，但有一种方法可以使其处理负边缘代价无论何时更新节点，都将更新的节点放回队列中然而，这究竟是真正的dijkstra还是一辆有优先权排队的贝尔曼福特还存在争议。
例如，考虑这个图：
1-2（100）
2-3（-200）
1-3（50）
3-4（100）
经典的dijkstra将设置d[1]=0，d[2]=100，d[3]=50，d[4]=150，d[3]=-100并停止。但是，当设置d[3]=-100时，将3添加回队列并继续算法。这将得到d[4]=0，这是正确的。但我不确定这是否被认为是“dijkstra算法”。
至于贝尔曼福特，图表不一定要被引导，（负成本循环，其他周期无论如何都没有区别）循环可以存在，只是确保你检测到周期。从队列中提取节点n次时会检测到一个循环，其中n是节点数你可以做同样的检查来检测一个周期在“修改Dijkstra的算法”我概述了上述。
floyd warshall-成本是节点数量的立方。除了非常小的图之外，其他任何东西都没有效率。它假定没有负成本周期，但您可以使用它来检测此类周期，请参见wikipedia。
mst-当边数接近o（n）而不是o（n2）时，使用kruskal。否则使用prim。这两种方法都适用于任何类型的图，即使它们包含负边权和圈。
另一个我个人非常喜欢的最短路径算法是Dial's algorithm我喜欢把它想象成在图表上计数排序同时阅读this rather exhaustive paper。
关于algorithm - 我正在尝试建立所有图算法的限制列表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2607261/