Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9f8fd33

Browse files
vivaxytrekhleb
authored andcommitted
feat(algorithms): ✨Add Floyd-Warshall (trekhleb#97)
1 parent3e8540b commit9f8fd33

File tree

6 files changed

+194
-5
lines changed

6 files changed

+194
-5
lines changed

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,8 @@ a set of rules that precisely define a sequence of operations.
113113
*`A`[Hamiltonian Cycle](src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
114114
*`A`[Strongly Connected Components](src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
115115
*`A`[Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city
116-
***Uncategorized**
116+
*`A`[Floyd-Warshall algorithm](src/algorithms/graph/floyd-warshall) - a single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices
117+
***Uncategorized**
117118
*`B`[Tower of Hanoi](src/algorithms/uncategorized/hanoi-tower)
118119
*`B`[Square Matrix Rotation](src/algorithms/uncategorized/square-matrix-rotation) - in-place algorithm
119120
*`B`[Jump Game](src/algorithms/uncategorized/jump-game) - backtracking, dynamic programming (top-down + bottom-up) and greedy examples

‎README.zh-CN.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ _Read this in other languages:_
6969
*[归并排序](src/algorithms/sorting/merge-sort)
7070
*[快速排序](src/algorithms/sorting/quick-sort)
7171
*[希尔排序](src/algorithms/sorting/shell-sort)
72-
***树**
72+
***树**
7373
*[深度优先搜索](src/algorithms/tree/depth-first-search) (DFS)
7474
*[广度优先搜索](src/algorithms/tree/breadth-first-search) (BFS)
7575
***图**
@@ -87,7 +87,8 @@ _Read this in other languages:_
8787
*[哈密顿图](src/algorithms/graph/hamiltonian-cycle) - 恰好访问每个顶点一次
8888
*[强连通分量](src/algorithms/graph/strongly-connected-components) - Kosaraju算法
8989
*[旅行推销员问题](src/algorithms/graph/travelling-salesman) - 尽可能以最短的路线访问每个城市并返回原始城市
90-
***未分类**
90+
*[Floyd-Warshall algorithm](src/algorithms/graph/floyd-warshall) - 一次循环可以找出所有顶点之间的最短路径
91+
***未分类**
9192
*[汉诺塔](src/algorithms/uncategorized/hanoi-tower)
9293
*[八皇后问题](src/algorithms/uncategorized/n-queens)
9394
*[骑士巡逻](src/algorithms/uncategorized/knight-tour)

‎README.zh-TW.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -68,7 +68,7 @@ _Read this in other languages:_
6868
*[合併排序](src/algorithms/sorting/merge-sort)
6969
*[快速排序](src/algorithms/sorting/quick-sort)
7070
*[希爾排序](src/algorithms/sorting/shell-sort)
71-
***樹**
71+
***樹**
7272
*[深度優先搜尋](src/algorithms/tree/depth-first-search) (DFS)
7373
*[廣度優先搜尋](src/algorithms/tree/breadth-first-search) (BFS)
7474
***圖**
@@ -86,7 +86,8 @@ _Read this in other languages:_
8686
*[漢彌爾頓環](src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
8787
*[強連通組件](src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
8888
*[旅行推銷員問題](src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city
89-
***未分類**
89+
*[Floyd-Warshall algorithm](src/algorithms/graph/floyd-warshall) - 一次循环可以找出所有頂點之间的最短路徑
90+
***未分類**
9091
*[河內塔](src/algorithms/uncategorized/hanoi-tower)
9192
*[N-皇后問題](src/algorithms/uncategorized/n-queens)
9293
*[騎士走棋盤](src/algorithms/uncategorized/knight-tour)
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
#Floyd–Warshall algorithm
2+
3+
##References
4+
5+
-[Wikipedia](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)
Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
importGraphVertexfrom'../../../../data-structures/graph/GraphVertex';
2+
importGraphEdgefrom'../../../../data-structures/graph/GraphEdge';
3+
importGraphfrom'../../../../data-structures/graph/Graph';
4+
importfloydWarshallfrom'../floydWarshall';
5+
6+
describe('floydWarshall',()=>{
7+
it('should find minimum paths to all vertices for undirected graph',()=>{
8+
constvertexA=newGraphVertex('A');
9+
constvertexB=newGraphVertex('B');
10+
constvertexC=newGraphVertex('C');
11+
constvertexD=newGraphVertex('D');
12+
constvertexE=newGraphVertex('E');
13+
constvertexF=newGraphVertex('F');
14+
constvertexG=newGraphVertex('G');
15+
constvertexH=newGraphVertex('H');
16+
17+
constedgeAB=newGraphEdge(vertexA,vertexB,4);
18+
constedgeAE=newGraphEdge(vertexA,vertexE,7);
19+
constedgeAC=newGraphEdge(vertexA,vertexC,3);
20+
constedgeBC=newGraphEdge(vertexB,vertexC,6);
21+
constedgeBD=newGraphEdge(vertexB,vertexD,5);
22+
constedgeEC=newGraphEdge(vertexE,vertexC,8);
23+
constedgeED=newGraphEdge(vertexE,vertexD,2);
24+
constedgeDC=newGraphEdge(vertexD,vertexC,11);
25+
constedgeDG=newGraphEdge(vertexD,vertexG,10);
26+
constedgeDF=newGraphEdge(vertexD,vertexF,2);
27+
constedgeFG=newGraphEdge(vertexF,vertexG,3);
28+
constedgeEG=newGraphEdge(vertexE,vertexG,5);
29+
30+
constgraph=newGraph();
31+
graph
32+
.addVertex(vertexH)
33+
.addEdge(edgeAB)
34+
.addEdge(edgeAE)
35+
.addEdge(edgeAC)
36+
.addEdge(edgeBC)
37+
.addEdge(edgeBD)
38+
.addEdge(edgeEC)
39+
.addEdge(edgeED)
40+
.addEdge(edgeDC)
41+
.addEdge(edgeDG)
42+
.addEdge(edgeDF)
43+
.addEdge(edgeFG)
44+
.addEdge(edgeEG);
45+
46+
const{ distances, previousVertices}=floydWarshall(graph);
47+
48+
constvertices=graph.getAllVertices();
49+
constvertexAIndex=vertices.indexOf(vertexA);
50+
constvl=vertices.length;
51+
52+
expect(distances[vertexAIndex][vertices.indexOf(vertexH)][vl]).toBe(Infinity);
53+
expect(distances[vertexAIndex][vertexAIndex][vl]).toBe(0);
54+
expect(distances[vertexAIndex][vertices.indexOf(vertexB)][vl]).toBe(4);
55+
expect(distances[vertexAIndex][vertices.indexOf(vertexE)][vl]).toBe(7);
56+
expect(distances[vertexAIndex][vertices.indexOf(vertexC)][vl]).toBe(3);
57+
expect(distances[vertexAIndex][vertices.indexOf(vertexD)][vl]).toBe(9);
58+
expect(distances[vertexAIndex][vertices.indexOf(vertexG)][vl]).toBe(12);
59+
expect(distances[vertexAIndex][vertices.indexOf(vertexF)][vl]).toBe(11);
60+
61+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexF)][vl]).toBe(vertexD);
62+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexD)][vl]).toBe(vertexB);
63+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexB)][vl]).toBe(vertexA);
64+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexG)][vl]).toBe(vertexE);
65+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexC)][vl]).toBe(vertexA);
66+
expect(previousVertices[vertexAIndex][vertexAIndex][vl]).toBe(null);
67+
expect(previousVertices[vertexAIndex][vertices.indexOf(vertexH)][vl]).toBe(null);
68+
});
69+
70+
it('should find minimum paths to all vertices for directed graph with negative edge weights',()=>{
71+
constvertexS=newGraphVertex('S');
72+
constvertexE=newGraphVertex('E');
73+
constvertexA=newGraphVertex('A');
74+
constvertexD=newGraphVertex('D');
75+
constvertexB=newGraphVertex('B');
76+
constvertexC=newGraphVertex('C');
77+
constvertexH=newGraphVertex('H');
78+
79+
constedgeSE=newGraphEdge(vertexS,vertexE,8);
80+
constedgeSA=newGraphEdge(vertexS,vertexA,10);
81+
constedgeED=newGraphEdge(vertexE,vertexD,1);
82+
constedgeDA=newGraphEdge(vertexD,vertexA,-4);
83+
constedgeDC=newGraphEdge(vertexD,vertexC,-1);
84+
constedgeAC=newGraphEdge(vertexA,vertexC,2);
85+
constedgeCB=newGraphEdge(vertexC,vertexB,-2);
86+
constedgeBA=newGraphEdge(vertexB,vertexA,1);
87+
88+
constgraph=newGraph(true);
89+
graph
90+
.addVertex(vertexH)
91+
.addEdge(edgeSE)
92+
.addEdge(edgeSA)
93+
.addEdge(edgeED)
94+
.addEdge(edgeDA)
95+
.addEdge(edgeDC)
96+
.addEdge(edgeAC)
97+
.addEdge(edgeCB)
98+
.addEdge(edgeBA);
99+
100+
const{ distances, previousVertices}=floydWarshall(graph);
101+
102+
constvertices=graph.getAllVertices();
103+
constvertexSIndex=vertices.indexOf(vertexS);
104+
constvl=vertices.length;
105+
106+
expect(distances[vertexSIndex][vertices.indexOf(vertexH)][vl]).toBe(Infinity);
107+
expect(distances[vertexSIndex][vertexSIndex][vl]).toBe(0);
108+
expect(distances[vertexSIndex][vertices.indexOf(vertexA)][vl]).toBe(5);
109+
expect(distances[vertexSIndex][vertices.indexOf(vertexB)][vl]).toBe(5);
110+
expect(distances[vertexSIndex][vertices.indexOf(vertexC)][vl]).toBe(7);
111+
expect(distances[vertexSIndex][vertices.indexOf(vertexD)][vl]).toBe(9);
112+
expect(distances[vertexSIndex][vertices.indexOf(vertexE)][vl]).toBe(8);
113+
114+
expect(previousVertices[vertexSIndex][vertices.indexOf(vertexH)][vl]).toBe(null);
115+
expect(previousVertices[vertexSIndex][vertexSIndex][vl]).toBe(null);
116+
expect(previousVertices[vertexSIndex][vertices.indexOf(vertexB)][vl]).toBe(vertexC);
117+
expect(previousVertices[vertexSIndex][vertices.indexOf(vertexC)][vl]).toBe(vertexA);
118+
expect(previousVertices[vertexSIndex][vertices.indexOf(vertexA)][vl]).toBe(vertexD);
119+
expect(previousVertices[vertexSIndex][vertices.indexOf(vertexD)][vl]).toBe(vertexE);
120+
});
121+
});
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
exportdefaultfunctionfloydWarshall(graph){
2+
constvertices=graph.getAllVertices();
3+
4+
// Three dimension matrices.
5+
constdistances=[];
6+
constpreviousVertices=[];
7+
8+
// There are k vertices, loop from 0 to k.
9+
for(letk=0;k<=vertices.length;k+=1){
10+
// Path starts from vertex i.
11+
vertices.forEach((vertex,i)=>{
12+
if(k===0){
13+
distances[i]=[];
14+
previousVertices[i]=[];
15+
}
16+
17+
// Path ends to vertex j.
18+
vertices.forEach((endVertex,j)=>{
19+
if(k===0){
20+
// Initialize distance and previousVertices array
21+
distances[i][j]=[];
22+
previousVertices[i][j]=[];
23+
24+
if(vertex===endVertex){
25+
// Distance to self as 0
26+
distances[i][j][k]=0;
27+
// Previous vertex to self as null
28+
previousVertices[i][j][k]=null;
29+
}else{
30+
constedge=graph.findEdge(vertex,endVertex);
31+
if(edge){
32+
// There is an edge from vertex i to vertex j.
33+
// Save distance and previous vertex.
34+
distances[i][j][k]=edge.weight;
35+
previousVertices[i][j][k]=vertex;
36+
}else{
37+
distances[i][j][k]=Infinity;
38+
previousVertices[i][j][k]=null;
39+
}
40+
}
41+
}else{
42+
// Compare distance from i to j, with distance from i to k - 1 and then from k - 1 to j.
43+
// Save the shortest distance and previous vertex
44+
// distance[i][j][k] = min( distance[i][k - 1][k - 1], distance[k - 1][j][k - 1] )
45+
if(distances[i][j][k-1]>distances[i][k-1][k-1]+distances[k-1][j][k-1]){
46+
distances[i][j][k]=distances[i][k-1][k-1]+distances[k-1][j][k-1];
47+
previousVertices[i][j][k]=previousVertices[k-1][j][k-1];
48+
}else{
49+
distances[i][j][k]=distances[i][j][k-1];
50+
previousVertices[i][j][k]=previousVertices[i][j][k-1];
51+
}
52+
}
53+
});
54+
});
55+
}
56+
57+
// Shortest distance from x to y: distance[x][y][k]
58+
// Previous vertex when shortest distance from x to y: previousVertices[x][y][k]
59+
return{ distances, previousVertices};
60+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp