algorithm - 我正在尝试构建所有图形算法的限制列表

Question

Single Source shortest Path

Dijkstra 的 - 有向和无向 - 仅适用于正边权重 - 循环 ??

Bellman Ford - 指导 - 不应存在循环

All source shortest path

Floyd Warshall - 无信息

Minimum Spanning Tree 

(没有关于边权重或图形或循环性质的信息)

克鲁斯卡尔的

Prim's - 无向

巴鲁夫卡的

Answer 1

我不确定问题是什么，但这里是...

Dijkstra 算法的经典实现只能处理正边权重，但有一种方法可以使其处理负边成本。每当您更新节点时，将更新的节点放回队列中。然而，这究竟是 Dijkstra 还是带有优先队列的 Bellman-Ford 是有争议的。

例如考虑这张图:

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 算法”。

至于Bellman-Ford，这个图不一定非要有向，(负成本周期，其他周期反正没什么区别)周期是可以存在的，只要确保检测到周期即可。当您从队列中提取节点 n 次时，将检测到循环，其中 n 是节点数。您可以执行相同的检查来检测我上面概述的“修改后的 Dijkstra 算法”中的循环。

Floyd Warshall - 成本是节点数量的立方。除了非常小的图形外，其他任何东西都效率低下。它假定没有负成本周期，但您可以使用它来检测此类周期，请参阅 wikipedia .

MST - 当边数接近 O(n) 而不是 O(n²) 时使用 Kruskal。否则使用 Prim 的。两者都适用于任何类型的图，即使它们包含负边权重和循环。

另一个我个人非常喜欢的最短路径算法是Dial's algorithm .我喜欢把它想象成图表上的计数排序。另请阅读 this rather exhaustive paper .