1 Star 0 Fork 79

zhizou/javascript-algorithms

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
Loading...
README

Floyd–Warshall Algorithm

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.

Algorithm

The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with O(|V|^3) comparisons in a graph. This is remarkable considering that there may be up to |V|^2 edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.

Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1, 2, ..., k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices in {1, 2, ..., N}.

Recursive Formula

Recursive Formula Recursive Formula

This formula is the heart of the Floyd–Warshall algorithm.

Example

The algorithm above is executed on the graph on the left below:

Example

In the tables below i is row numbers and j is column numbers.

k = 0

1 2 3 4
1 0 −2
2 4 0 3
3 0 2
4 −1 0

k = 1

1 2 3 4
1 0 −2
2 4 0 2
3 0 2
4 0

k = 2

1 2 3 4
1 0 −2
2 4 0 2
3 0 2
4 3 −1 1 0

k = 3

1 2 3 4
1 0 −2 0
2 4 0 2 4
3 0 2
4 3 −1 1 0

k = 4

1 2 3 4
1 0 −1 −2 0
2 4 0 2 4
3 5 1 0 2
4 3 −1 1 0

References

马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
JavaScript
1
https://gitee.com/zhizous/javascript-algorithms.git
git@gitee.com:zhizous/javascript-algorithms.git
zhizous
javascript-algorithms
javascript-algorithms
master

搜索帮助