Content deleted Content added
Line 52:
: Dear non-account user, a request: before going back and making the same edit again, could we instead try to find common understanding? In particular, what do you think the symbols "{1,2,3}" represent? --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 01:21, 17 May 2015 (UTC)
there is no need to "know" what it means because it says what it is, aand what it says is WRONG. In fact, the __entire__ article is wrong.
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
Example
The algorithm above is executed on the graph on the left below:
Floyd-Warshall example.svg
Note - you have an EXMAMPLE pf K=0
K NEVER equals zero ... K starts at 1.
Prior to the first iteration of the outer loop, labeled k=0 above,
Yeah - that si WRONG, k is 1.
the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found.
WRONG, the paths do NOT go through that set.
Finally, at k=4, all shortest paths are found.
So the whole thing needs a rewrite. Try starting with Cormen....
| |||