## Shortest Path (Floyd-Warshall Algorithm)

Finding the shortest path between two nodes, or points on a graph, is a popular problem in computer science. For example, given the graph:

3 2 2

[1]-----[2]------[3]-----[4]

\ / \ /

7\ /4 \3 / 2

\ / \ /

[5]-----[6]------[7]

1 2

where [1] and [2] are nodes and the edges have distance, what is the shortest distance from [1] to [6]? Or from [2] to [7]? The Floyd-Warshall algorithm finds the all-pairs shortest path, meaning that after the algorithm is complete, you can find the shortest distance from any node to any other node.

First, we have to represent the graph in a data structure. We will use the adjacency matrix, a two-dimensional array path where

path[i][j] is the current shortest distance from i to j. path[i][i]=0 (distance from a node to itself is 0) and nodes that aren't connected yet are set to infinity. After initializing this graph, path=

{0, 3, inf, inf, 7, inf, inf}

{3, 0, 2, inf, 4, 3, inf}

{inf, 2, 0, 2, inf, inf, inf}

{inf, inf, 2, 0, inf, inf, 2}

{7, 4, inf, inf, 0, 1, inf}

{inf, 3, inf, inf, 1, 0, 2}

{inf, inf, inf, 2, inf, 2, 0}

where infinity is usually Integer.MAX_VALUE. Floyd-Warshall works by looping thorugh all elements of path. The minimum distance from i to j must be the minimum of path[i][j], path[i][k]+path[k][j] for all values of k. This is because that is the only way to get from i to j, through another node. The resultant algorithm is very simple and is 0(n^3) time.

public static void floydwarshall(int[][]path){

for(int k=0;k<path.length;k++){

for(int i=0;i<path.length;i++){

for(int j=0;j<path.length;j++){

path[i][j]=Math.min(path[i][j],path[i][k]+path[k][j]);

}

}

}

}

After calling floydwarshall(), the path matrix from before now looks like:

{ 0, 3, 5, 7, 7, 6, 8 }

{ 3, 0, 2, 4, 4, 3, 5 }

{ 5, 2, 0, 2, 6, 5, 4 }

{ 7, 4, 2, 0, 5, 4, 2 }

{ 7, 4, 6, 5, 0, 1, 3 }

{ 6, 3, 5, 4, 1, 0, 2 }

{ 8, 5, 4, 2, 3, 2, 0 }

So, the minimum distance from node 1 to 6 is path[1-1][6-1]=6 and the minimum distance from node 2 to 7 is path[2-1][7-1]=5 (we subtract one because of matrix indexes). Check to confirm if the algorithm was written correctly. Floyd-Warshall is a very powerful algorithm that requires fairly low time complexity considering how difficult the all-pairs shortest path problem looks at first.

3 2 2

[1]-----[2]------[3]-----[4]

\ / \ /

7\ /4 \3 / 2

\ / \ /

[5]-----[6]------[7]

1 2

where [1] and [2] are nodes and the edges have distance, what is the shortest distance from [1] to [6]? Or from [2] to [7]? The Floyd-Warshall algorithm finds the all-pairs shortest path, meaning that after the algorithm is complete, you can find the shortest distance from any node to any other node.

First, we have to represent the graph in a data structure. We will use the adjacency matrix, a two-dimensional array path where

path[i][j] is the current shortest distance from i to j. path[i][i]=0 (distance from a node to itself is 0) and nodes that aren't connected yet are set to infinity. After initializing this graph, path=

{0, 3, inf, inf, 7, inf, inf}

{3, 0, 2, inf, 4, 3, inf}

{inf, 2, 0, 2, inf, inf, inf}

{inf, inf, 2, 0, inf, inf, 2}

{7, 4, inf, inf, 0, 1, inf}

{inf, 3, inf, inf, 1, 0, 2}

{inf, inf, inf, 2, inf, 2, 0}

where infinity is usually Integer.MAX_VALUE. Floyd-Warshall works by looping thorugh all elements of path. The minimum distance from i to j must be the minimum of path[i][j], path[i][k]+path[k][j] for all values of k. This is because that is the only way to get from i to j, through another node. The resultant algorithm is very simple and is 0(n^3) time.

public static void floydwarshall(int[][]path){

for(int k=0;k<path.length;k++){

for(int i=0;i<path.length;i++){

for(int j=0;j<path.length;j++){

path[i][j]=Math.min(path[i][j],path[i][k]+path[k][j]);

}

}

}

}

After calling floydwarshall(), the path matrix from before now looks like:

{ 0, 3, 5, 7, 7, 6, 8 }

{ 3, 0, 2, 4, 4, 3, 5 }

{ 5, 2, 0, 2, 6, 5, 4 }

{ 7, 4, 2, 0, 5, 4, 2 }

{ 7, 4, 6, 5, 0, 1, 3 }

{ 6, 3, 5, 4, 1, 0, 2 }

{ 8, 5, 4, 2, 3, 2, 0 }

So, the minimum distance from node 1 to 6 is path[1-1][6-1]=6 and the minimum distance from node 2 to 7 is path[2-1][7-1]=5 (we subtract one because of matrix indexes). Check to confirm if the algorithm was written correctly. Floyd-Warshall is a very powerful algorithm that requires fairly low time complexity considering how difficult the all-pairs shortest path problem looks at first.

Provided by website-hit-counters.com site. |