Loading AI tools
来自维基百科,自由的百科全书
Floyd-Warshall算法(英语:Floyd-Warshall algorithm),中文亦称弗洛伊德算法或佛洛依德算法[1],是解决任意两点间的最短路径的一种算法[2],可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包[3]。
设为从到的只以集合中的节点为中间节点的最短路径的长度。
因此,。
在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。
Floyd-Warshall算法的伪代码描述如下:
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if
其中dist[i][j]
表示由点到点的代价,当其为 ∞ 表示两点之间没有任何连接。
Floyd算法在不同的编程语言中均有大量的实现方法:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.