我们知道求图的最短路有Dijkstra应用于无负权的算法，也有应用于有负权的Bellman0-Ford算法，但是当源点有多个呢？难道我们要调用n次的Dijkstra算法？有没有其它的算法呢？这是当然的，Floyd-Warshall就是用来解决这个问题的，也许有学过的人会说这个算法的效率太低，为O(n^3)但是，当摊销到每一条路上时，其效率为O(V)还是很高的，很实用的一个算法。我们知道求图的最短路有Dijkstra应用于无负权的算法，也有应用于有负权的Bellman0-
阅读背景：
图的多源点最短路问题和传递闭包之Floyd-Warshall算法 By ACReaper
来源：互联网
分享到：
