Floyd Warshall

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

There are many notable algorithms to calculate the shortest path between vertices in a graph. Most are based on single source to a set of destination vertices. Examples of such famous algorithms include Dijkstra’s, Bellman-Ford and even Breadth First Search for weightless graphs. However, sometimes we wish to calculate the shortest paths between all pairs of vertices. An easy way to calculate this is to loop through each possible pair of vertices and run a Dijkstra through it. However, there exists a more efficient way to calculate this in n^3 time complexity.

Floyd-Warshall algorithm, a formula consisting of the core is very simple. A, B, C, I suppose we have 3 points. In this case, the shortest distance between A and C (distance (A, C), distance (A, B) + distance (B, C)) is up. Floyd-Warshall’ı need to apply to a table. The size of this table, depending on the number of points to be determined. We got one point, the table size N * N N

int[,] table = new int[5,5];

On the basis of the algorithm used for the function of the input for this table are the values at the maximum. The distance of each point of self-0, the distance to other points, we will begin by accepting the infinite.

int INFINITY = 9999999;
int N = 5;
for (int i = 0; i < N; i++)
  for(int j = 0; j < N; j++)
    table[i,j] = i == j ? 0 : INFINITY;

After this operation, the value of the table will be as follows.

table 1 2 3 4 5
1 0 INF INF INF INF
2 INF 0 INF INF INF
3 INF INF 0 INF INF
4 INF INF INF 0 INF
5 INF INF INF INF 0

Second, to keep the connection between the points and to build the matrix of contiguity for questioning. If you have an edge from one point to another entry in the table that would give a value. For example, point 3 and point 4, one side has 2 points. Therefore, our statements [2,3] = [2.4] = 1 = [3.2] = [4.2]. Grafımız no way we obtain for the diagonal matrix based on contiguity should be symmetrical. 1 to 4, because to have the edge in the 4 to 1, this also means there are also edges. Our example is a way you could tell it had graphs. After this, the final version of the table will be as follows:

table 1 2 3 4 5
1 0 INF INF 1 INF
2 INF 0 1 1 INF
3 INF 1 0 1 INF
4 1 1 1 0 1
5 INF INF INF 1 0

Floyd-Warshall can now apply the formula:

for( int k = 0; k &lt; N; k++)
for( int i = 0; i &lt; N; i++)
for( int j = 0; j &lt; N; j++)
table[i,j] = Math.Min(table[i,j], table[i,k] + table[k,j]);

That’s it. After this, our table will be as final.

table 1 2 3 4 5
1 0 2 2 1 2
2 2 0 1 1 2
3 2 1 0 1 2
4 1 1 1 0 1
5 2 2 2 1 0

Now using the table between the two points (a, b) can query the shortest distance. table [a, b] = table [b, a].

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s