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

Commitdca7f6f

Browse files
committed
Refactor Floyd-Warshall.
1 parent994ac27 commitdca7f6f

File tree

2 files changed

+167
-81
lines changed

2 files changed

+167
-81
lines changed

‎src/algorithms/graph/floyd-warshall/__test__/floydWarshall.test.js

Lines changed: 108 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -46,25 +46,93 @@ describe('floydWarshall', () => {
4646
const{ distances, previousVertices}=floydWarshall(graph);
4747

4848
constvertices=graph.getAllVertices();
49+
50+
constvertexAIndex=vertices.indexOf(vertexA);
51+
constvertexBIndex=vertices.indexOf(vertexB);
52+
constvertexCIndex=vertices.indexOf(vertexC);
53+
constvertexDIndex=vertices.indexOf(vertexD);
54+
constvertexEIndex=vertices.indexOf(vertexE);
55+
constvertexFIndex=vertices.indexOf(vertexF);
56+
constvertexGIndex=vertices.indexOf(vertexG);
57+
constvertexHIndex=vertices.indexOf(vertexH);
58+
59+
expect(distances[vertexAIndex][vertexHIndex]).toBe(Infinity);
60+
expect(distances[vertexAIndex][vertexAIndex]).toBe(0);
61+
expect(distances[vertexAIndex][vertexBIndex]).toBe(4);
62+
expect(distances[vertexAIndex][vertexEIndex]).toBe(7);
63+
expect(distances[vertexAIndex][vertexCIndex]).toBe(3);
64+
expect(distances[vertexAIndex][vertexDIndex]).toBe(9);
65+
expect(distances[vertexAIndex][vertexGIndex]).toBe(12);
66+
expect(distances[vertexAIndex][vertexFIndex]).toBe(11);
67+
68+
expect(previousVertices[vertexAIndex][vertexFIndex]).toBe(vertexD);
69+
expect(previousVertices[vertexAIndex][vertexDIndex]).toBe(vertexB);
70+
expect(previousVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
71+
expect(previousVertices[vertexAIndex][vertexGIndex]).toBe(vertexE);
72+
expect(previousVertices[vertexAIndex][vertexCIndex]).toBe(vertexA);
73+
expect(previousVertices[vertexAIndex][vertexAIndex]).toBe(null);
74+
expect(previousVertices[vertexAIndex][vertexHIndex]).toBe(null);
75+
});
76+
77+
it('should find minimum paths to all vertices for directed graph',()=>{
78+
constvertexA=newGraphVertex('A');
79+
constvertexB=newGraphVertex('B');
80+
constvertexC=newGraphVertex('C');
81+
constvertexD=newGraphVertex('D');
82+
83+
constedgeAB=newGraphEdge(vertexA,vertexB,3);
84+
constedgeBA=newGraphEdge(vertexB,vertexA,8);
85+
constedgeAD=newGraphEdge(vertexA,vertexD,7);
86+
constedgeDA=newGraphEdge(vertexD,vertexA,2);
87+
constedgeBC=newGraphEdge(vertexB,vertexC,2);
88+
constedgeCA=newGraphEdge(vertexC,vertexA,5);
89+
constedgeCD=newGraphEdge(vertexC,vertexD,1);
90+
91+
constgraph=newGraph(true);
92+
93+
// Add vertices first just to have them in desired order.
94+
graph
95+
.addVertex(vertexA)
96+
.addVertex(vertexB)
97+
.addVertex(vertexC)
98+
.addVertex(vertexD);
99+
100+
// Now, when vertices are in correct order let's add edges.
101+
graph
102+
.addEdge(edgeAB)
103+
.addEdge(edgeBA)
104+
.addEdge(edgeAD)
105+
.addEdge(edgeDA)
106+
.addEdge(edgeBC)
107+
.addEdge(edgeCA)
108+
.addEdge(edgeCD);
109+
110+
const{ distances, previousVertices}=floydWarshall(graph);
111+
112+
constvertices=graph.getAllVertices();
113+
49114
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);
115+
constvertexBIndex=vertices.indexOf(vertexB);
116+
constvertexCIndex=vertices.indexOf(vertexC);
117+
constvertexDIndex=vertices.indexOf(vertexD);
118+
119+
expect(distances[vertexAIndex][vertexAIndex]).toBe(0);
120+
expect(distances[vertexAIndex][vertexBIndex]).toBe(3);
121+
expect(distances[vertexAIndex][vertexCIndex]).toBe(5);
122+
expect(distances[vertexAIndex][vertexDIndex]).toBe(6);
123+
124+
expect(distances).toEqual([
125+
[0,3,5,6],
126+
[5,0,2,3],
127+
[3,6,0,1],
128+
[2,5,7,0],
129+
]);
130+
131+
expect(previousVertices[vertexAIndex][vertexDIndex]).toBe(vertexC);
132+
expect(previousVertices[vertexAIndex][vertexCIndex]).toBe(vertexB);
133+
expect(previousVertices[vertexBIndex][vertexDIndex]).toBe(vertexC);
134+
expect(previousVertices[vertexAIndex][vertexAIndex]).toBe(null);
135+
expect(previousVertices[vertexAIndex][vertexBIndex]).toBe(vertexA);
68136
});
69137

70138
it('should find minimum paths to all vertices for directed graph with negative edge weights',()=>{
@@ -100,22 +168,28 @@ describe('floydWarshall', () => {
100168
const{ distances, previousVertices}=floydWarshall(graph);
101169

102170
constvertices=graph.getAllVertices();
171+
172+
constvertexAIndex=vertices.indexOf(vertexA);
173+
constvertexBIndex=vertices.indexOf(vertexB);
174+
constvertexCIndex=vertices.indexOf(vertexC);
175+
constvertexDIndex=vertices.indexOf(vertexD);
176+
constvertexEIndex=vertices.indexOf(vertexE);
177+
constvertexHIndex=vertices.indexOf(vertexH);
103178
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);
179+
180+
expect(distances[vertexSIndex][vertexHIndex]).toBe(Infinity);
181+
expect(distances[vertexSIndex][vertexSIndex]).toBe(0);
182+
expect(distances[vertexSIndex][vertexAIndex]).toBe(5);
183+
expect(distances[vertexSIndex][vertexBIndex]).toBe(5);
184+
expect(distances[vertexSIndex][vertexCIndex]).toBe(7);
185+
expect(distances[vertexSIndex][vertexDIndex]).toBe(9);
186+
expect(distances[vertexSIndex][vertexEIndex]).toBe(8);
187+
188+
expect(previousVertices[vertexSIndex][vertexHIndex]).toBe(null);
189+
expect(previousVertices[vertexSIndex][vertexSIndex]).toBe(null);
190+
expect(previousVertices[vertexSIndex][vertexBIndex]).toBe(vertexC);
191+
// expect(previousVertices[vertexSIndex][vertexCIndex].getKey()).toBe(vertexA.getKey());
192+
expect(previousVertices[vertexSIndex][vertexAIndex]).toBe(vertexD);
193+
expect(previousVertices[vertexSIndex][vertexDIndex]).toBe(vertexE);
120194
});
121195
});
Lines changed: 59 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -1,60 +1,72 @@
1+
/**
2+
*@param {Graph} graph
3+
*@return {{distances: number[][], previousVertices: GraphVertex[][]}}
4+
*/
15
exportdefaultfunctionfloydWarshall(graph){
6+
// Get all graph vertices.
27
constvertices=graph.getAllVertices();
38

4-
// Three dimension matrices.
5-
constdistances=[];
6-
constpreviousVertices=[];
9+
// Init previous vertices matrix with nulls meaning that there are no
10+
// previous vertices exist that will give us shortest path.
11+
constpreviousVertices=Array(vertices.length).fill(null).map(()=>{
12+
returnArray(vertices.length).fill(null);
13+
});
714

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-
}
15+
// Init distances matrix with Infinities meaning there are no paths
16+
// between vertices exist so far.
17+
constdistances=Array(vertices.length).fill(null).map(()=>{
18+
returnArray(vertices.length).fill(Infinity);
19+
});
1620

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]=[];
21+
// Init distance matrix with the distance we already now (from existing edges).
22+
// And also init previous vertices from the edges.
23+
vertices.forEach((startVertex,startIndex)=>{
24+
vertices.forEach((endVertex,endIndex)=>{
25+
if(startVertex===endVertex){
26+
// Distance to the vertex itself is 0.
27+
distances[startIndex][endIndex]=0;
28+
}else{
29+
// Find edge between the start and end vertices.
30+
constedge=graph.findEdge(startVertex,endVertex);
2331

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-
}
32+
if(edge){
33+
// There is an edge from vertex with startIndex to vertex with endIndex.
34+
// Save distance and previous vertex.
35+
distances[startIndex][endIndex]=edge.weight;
36+
previousVertices[startIndex][endIndex]=startVertex;
4137
}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-
}
38+
distances[startIndex][endIndex]=Infinity;
39+
}
40+
}
41+
});
42+
});
43+
44+
// Now let's go to the core of the algorithm.
45+
// Let's all pair of vertices (from start to end ones) and try to check if there
46+
// is a shorter path exists between them via middle vertex. Middle vertex may also
47+
// be one of the graph vertices. As you may see now we're going to have three
48+
// loops over all graph vertices: for start, end and middle vertices.
49+
vertices.forEach((middleVertex,middleIndex)=>{
50+
// Path starts from startVertex with startIndex.
51+
vertices.forEach((startVertex,startIndex)=>{
52+
// Path ends to endVertex with endIndex.
53+
vertices.forEach((endVertex,endIndex)=>{
54+
// Compare existing distance from startVertex to endVertex, with distance
55+
// from startVertex to endVertex but via middleVertex.
56+
// Save the shortest distance and previous vertex that allows
57+
// us to have this shortest distance.
58+
constdistViaMiddle=distances[startIndex][middleIndex]+distances[middleIndex][endIndex];
59+
60+
if(distances[startIndex][endIndex]>distViaMiddle){
61+
// We've found a shortest pass via middle vertex.
62+
distances[startIndex][endIndex]=distViaMiddle;
63+
previousVertices[startIndex][endIndex]=middleVertex;
5264
}
5365
});
5466
});
55-
}
67+
});
5668

57-
// Shortest distance from x to y: distance[x][y][k]
58-
// Previous vertexwhen shortestdistance from x to y: previousVertices[x][y][k]
69+
// Shortest distance from x to y: distance[x][y].
70+
// Previous vertexof shortestpath from x to y: previousVertices[x][y].
5971
return{ distances, previousVertices};
6072
}

0 commit comments

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