Lecture
The most commonly used name for the method comes from the two American researchers Robert Floyd and Stephen Warshall, who discovered it independently in 1962. Other, less common names are the Roy–Warshall algorithm or the Roy–Floyd algorithm. Roy is the surname of a professor who developed a similar algorithm 3 years earlier (in 1959), but his discovery went unnoticed. The Floyd–Warshall algorithm is a dynamic programming algorithm for computing the shortest path values for every vertex of a graph. The method works on weighted graphs with positive and negative edge weights, but without negative cycles, making it more general than Dijkstra's algorithm, since the latter does not work with negative edge weights and, moreover, its classic implementation determines the optimal distances from a single vertex to all others.
To implement the Floyd–Warshall algorithm, let's form the adjacency matrix D[][] of the graph G=(V, E), in which each vertex is numbered from 1 to |V|. This matrix has size |V|´|V|, and each of its elements D[i][j] is assigned the weight of the edge going from vertex i to vertex j. As the algorithm runs, this matrix will be overwritten: each of its cells will receive the value that determines the optimal path length from vertex i to vertex j (avoiding the allocation of a separate array for this purpose saves memory and time). Now, before writing the main part of the algorithm, we need to work out the contents of the shortest-path matrix. Since each element D[i][j] must contain the shortest of the available routes, we can immediately say that for a single vertex it equals zero, even if it has a loop (negative cycles are not considered), hence all elements of the main diagonal (D[i][i]) must be set to zero. And so that the zero off-diagonal elements (the adjacency matrix could have zeros in places where there is no direct edge between vertices i and j) change their value where possible, let's set them equal to infinity, which in the program can be, for example, the maximum possible path length in the graph, or simply a large number.
The key part of the algorithm, consisting of three loops, an expression, and a conditional statement, is written quite compactly:
For k from 1 to |V| do
For i from 1 to |V| do
For j from 1 to |V| do
If D[i][k]+D[k][j]
The shortest path from vertex i to vertex j can pass either only through them, or through a set of other vertices k∈(1, …, |V|). The optimal path from i to j either does not pass through k, or it does. Concluding that the second case holds means establishing that such a path goes from i to k, and then from k to j, so the value of the shortest path D[i][j] should be replaced with the sum D[i][k]+D[k][j].
Let's look at the complete code for the Floyd–Warshall algorithm in C++ and Pascal, and then examine in detail the sequence of actions it performs.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include "stdafx.h"
#include using namespace std; const int maxV=1000; int i, j, n; int GR[maxV][maxV]; //Floyd-Warshall algorithm void FU(int D[][maxV], int V) { int k; for (i=0; i for (k=0; kfor (i=0; ifor (j=0; jif (D[i][k] && D[k][j] && i!=j) if (D[i][k]+D[k][j]D[i][j]=D[i][k]+D[k][j]; for (i=0; i{ for (j=0; jcout<} } //main function void main() { setlocale(LC_ALL, "Rus"); cout<<"Number of vertices in the graph > "; cin>>n; cout<<"Enter the edge weight matrix:\n"; for (i=0; ifor (j=0; j{ cout<<"GR["< "; cin>>GR[i][j]; } cout<<"Shortest path matrix:"<FU(GR, n); system("pause>>void"); } |
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
program Floyd_Uorshell;
uses crt; const maxV=1000; type matr=array[1..maxV, 1..maxV] of integer; var i, j, n, inf: integer; GR: matr; {Floyd-Warshall algorithm} Procedure FU(D: matr; V: integer); var k: integer; begin inf:=1000000; for i:=1 to V do D[i, i]:=0; for k:=1 to V do for i:=1 to V do for j:=1 to V do if (D[i, k]<>0) and (D[k, j]<>0) and (i<>j) then if (D[i, k]+D[k, j]D[i, j]:=D[i, k]+D[k, j]; for i:=1 to V do begin for j:=1 to V do write(D[i, j]:4); writeln; ; end; end; {main block of the program} begin clrscr; write('Number of vertices in the graph > '); readln(n); writeln('Enter the edge weight matrix:'); for i:=1 to n do for j:=1 to n do begin write('GR[', i, '][', j, '] > '); read(GR[i, j]); end; writeln('Shortest path matrix:'); FU(GR, n); end. |
Suppose that the following matrix was given as the adjacency matrix, each element of which stores the weight of some edge:
| 0 | 9 | 2 |
| 1 | 0 | 4 |
| 2 | 4 | 0 |
The number of vertices in the graph represented by this matrix is equal to 3, and moreover an edge exists between every two vertices. Here is this graph itself:
The algorithm's task: rewrite this matrix so that each cell, instead of the weight of the edge from i to j, contains the shortest path from i to j. A very small graph was chosen for the example, so it's not surprising if the matrix retains its original state. But the test results of the program show that two values in it are replaced. The following diagram will help analyze this specific example.
This table shows 27 steps of executing the main part of the algorithm. There are that many because the running time of the method is O(|V|3). Our graph has 3 vertices, and 33=27. The first replacement occurs at the iteration where k=1, i=2, and j=3. At that moment D = 1, D = 2, D = 4. The condition is true, i.e., D + D = 3, and 3<4, therefore the matrix element D receives a new value. The next step, where the condition is also true, brings a change to the element located at the intersection of the second row and third column.
Comments