/* package whatever; // don't place package name! */
class FloydWarshell
{
// Recursive Function to print path of given
// vertex u from source vertex v
private static void printPath( int [ ] [ ] path, int v, int u)
{
if ( path[ v] [ u] == v)
return ;
printPath( path, v, path[ v] [ u] ) ;
System .
out .
print ( path
[ v
] [ u
] + " " ) ; }
// Function to print the shortest cost with path
// information between all pairs of vertices
private static void printSolution( int [ ] [ ] cost, int [ ] [ ] path, int N)
{
for ( int v = 0 ; v < N; v++ )
{
for ( int u = 0 ; u < N; u++ )
{
if ( u != v && path[ v] [ u] != - 1 )
{
System .
out .
print ( "Shortest Path from vertex " + v
+ " to vertex " + u + " is (" + v + " " ) ;
printPath( path, v, u) ;
}
}
}
}
// Function to run Floyd-Warshell algorithm
public static void FloydWarshell( int [ ] [ ] adjMatrix, int N)
{
// cost[] and parent[] stores shortest-path
// (shortest-cost/shortest route) information
int [ ] [ ] cost = new int [ N] [ N] ;
int [ ] [ ] path = new int [ N] [ N] ;
// initialize cost[] and parent[]
for ( int v = 0 ; v < N; v++ )
{
for ( int u = 0 ; u < N; u++ )
{
// initally cost would be same as weight
// of the edge
cost[ v] [ u] = adjMatrix[ v] [ u] ;
if ( v == u)
path[ v] [ u] = 0 ;
else if ( cost
[ v
] [ u
] != Integer .
MAX_VALUE ) path[ v] [ u] = v;
else
path[ v] [ u] = - 1 ;
}
}
// run Floyd-Warshell
for ( int k = 0 ; k < N; k++ )
{
for ( int v = 0 ; v < N; v++ )
{
for ( int u = 0 ; u < N; u++ )
{
// If vertex k is on the shortest path from v to u,
// then update the value of cost[v][u], path[v][u]
if ( cost
[ v
] [ k
] != Integer .
MAX_VALUE && ( cost[ v] [ k] + cost[ k] [ u] < cost[ v] [ u] ) )
{
cost[ v] [ u] = cost[ v] [ k] + cost[ k] [ u] ;
path[ v] [ u] = path[ k] [ u] ;
}
}
// if diagonal elements become negative, the
// graph contains a negative weight cycle
if ( cost[ v] [ v] < 0 )
{
System .
out .
println ( "Negative Weight Cycle Found!!" ) ; return ;
}
}
}
// Print the shortest path between all pairs of vertices
printSolution( cost, path, N) ;
}
public static void main
( String [ ] args
) {
// Number of vertices in the adjMatrix
final int N = 4 ;
// given adjacency representation of matrix
int [ ] [ ] adjMatrix = new int [ ] [ ]
{
{ 0 , M, - 2 , M } ,
{ 4 , 0 , 3 , M } ,
{ M, M, 0 , 2 } ,
{ M, - 1 , M, 0 }
} ;
// Run Floyd Warshell algorithm
FloydWarshell( adjMatrix, N) ;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKY2xhc3MgRmxveWRXYXJzaGVsbAp7CiAgICAvLyBSZWN1cnNpdmUgRnVuY3Rpb24gdG8gcHJpbnQgcGF0aCBvZiBnaXZlbgogICAgLy8gdmVydGV4IHUgZnJvbSBzb3VyY2UgdmVydGV4IHYKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgcHJpbnRQYXRoKGludFtdW10gcGF0aCwgaW50IHYsIGludCB1KQogICAgewogICAgICAgIGlmIChwYXRoW3ZdW3VdID09IHYpCiAgICAgICAgICAgIHJldHVybjsKCiAgICAgICAgcHJpbnRQYXRoKHBhdGgsIHYsIHBhdGhbdl1bdV0pOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnQocGF0aFt2XVt1XSArICIgIik7CiAgICB9CgogICAgLy8gRnVuY3Rpb24gdG8gcHJpbnQgdGhlIHNob3J0ZXN0IGNvc3Qgd2l0aCBwYXRoCiAgICAvLyBpbmZvcm1hdGlvbiBiZXR3ZWVuIGFsbCBwYWlycyBvZiB2ZXJ0aWNlcwogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBwcmludFNvbHV0aW9uKGludFtdW10gY29zdCwgaW50W11bXSBwYXRoLCBpbnQgTikKICAgIHsKICAgICAgICBmb3IgKGludCB2ID0gMDsgdiA8IE47IHYrKykKICAgICAgICB7CiAgICAgICAgICAgIGZvciAoaW50IHUgPSAwOyB1IDwgTjsgdSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAodSAhPSB2ICYmIHBhdGhbdl1bdV0gIT0gLTEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludCgiU2hvcnRlc3QgUGF0aCBmcm9tIHZlcnRleCAiICsgdiArCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAiIHRvIHZlcnRleCAiICsgdSArICIgaXMgKCIgKyB2ICsgIiAiKTsKICAgICAgICAgICAgICAgICAgICBwcmludFBhdGgocGF0aCwgdiwgdSk7CiAgICAgICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHUgKyAiKSIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIEZ1bmN0aW9uIHRvIHJ1biBGbG95ZC1XYXJzaGVsbCBhbGdvcml0aG0KICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBGbG95ZFdhcnNoZWxsKGludFtdW10gYWRqTWF0cml4LCBpbnQgTikKICAgIHsKICAgICAgICAvLyBjb3N0W10gYW5kIHBhcmVudFtdIHN0b3JlcyBzaG9ydGVzdC1wYXRoCiAgICAgICAgLy8gKHNob3J0ZXN0LWNvc3Qvc2hvcnRlc3Qgcm91dGUpIGluZm9ybWF0aW9uCiAgICAgICAgaW50W11bXSBjb3N0ID0gbmV3IGludFtOXVtOXTsKICAgICAgICBpbnRbXVtdIHBhdGggPSBuZXcgaW50W05dW05dOwoKICAgICAgICAvLyBpbml0aWFsaXplIGNvc3RbXSBhbmQgcGFyZW50W10KICAgICAgICBmb3IgKGludCB2ID0gMDsgdiA8IE47IHYrKykKICAgICAgICB7CiAgICAgICAgICAgIGZvciAoaW50IHUgPSAwOyB1IDwgTjsgdSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvLyBpbml0YWxseSBjb3N0IHdvdWxkIGJlIHNhbWUgYXMgd2VpZ2h0CiAgICAgICAgICAgICAgICAvLyBvZiB0aGUgZWRnZQogICAgICAgICAgICAgICAgY29zdFt2XVt1XSA9IGFkak1hdHJpeFt2XVt1XTsKCiAgICAgICAgICAgICAgICBpZiAodiA9PSB1KQogICAgICAgICAgICAgICAgICAgIHBhdGhbdl1bdV0gPSAwOwogICAgICAgICAgICAgICAgZWxzZSBpZiAoY29zdFt2XVt1XSAhPSBJbnRlZ2VyLk1BWF9WQUxVRSkKICAgICAgICAgICAgICAgICAgICBwYXRoW3ZdW3VdID0gdjsKICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBwYXRoW3ZdW3VdID0gLTE7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIC8vIHJ1biBGbG95ZC1XYXJzaGVsbAogICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgTjsgaysrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgdiA9IDA7IHYgPCBOOyB2KyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IHUgPSAwOyB1IDwgTjsgdSsrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIC8vIElmIHZlcnRleCBrIGlzIG9uIHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gdiB0byB1LAogICAgICAgICAgICAgICAgICAgIC8vIHRoZW4gdXBkYXRlIHRoZSB2YWx1ZSBvZiBjb3N0W3ZdW3VdLCBwYXRoW3ZdW3VdCgogICAgICAgICAgICAgICAgICAgIGlmIChjb3N0W3ZdW2tdICE9IEludGVnZXIuTUFYX1ZBTFVFCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAmJiBjb3N0W2tdW3VdICE9IEludGVnZXIuTUFYX1ZBTFVFCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAmJiAoY29zdFt2XVtrXSArIGNvc3Rba11bdV0gPCBjb3N0W3ZdW3VdKSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvc3Rbdl1bdV0gPSBjb3N0W3ZdW2tdICsgY29zdFtrXVt1XTsKICAgICAgICAgICAgICAgICAgICAgICAgcGF0aFt2XVt1XSA9IHBhdGhba11bdV07CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIC8vIGlmIGRpYWdvbmFsIGVsZW1lbnRzIGJlY29tZSBuZWdhdGl2ZSwgdGhlCiAgICAgICAgICAgICAgICAvLyBncmFwaCBjb250YWlucyBhIG5lZ2F0aXZlIHdlaWdodCBjeWNsZQogICAgICAgICAgICAgICAgaWYgKGNvc3Rbdl1bdl0gPCAwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTmVnYXRpdmUgV2VpZ2h0IEN5Y2xlIEZvdW5kISEiKTsKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIC8vIFByaW50IHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gYWxsIHBhaXJzIG9mIHZlcnRpY2VzCiAgICAgICAgcHJpbnRTb2x1dGlvbihjb3N0LCBwYXRoLCBOKTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKQogICAgewogICAgICAgIC8vIE51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgYWRqTWF0cml4CiAgICAgICAgZmluYWwgaW50IE4gPSA0OwogICAgICAgIGludCBNID0gSW50ZWdlci5NQVhfVkFMVUU7CgogICAgICAgIC8vIGdpdmVuIGFkamFjZW5jeSByZXByZXNlbnRhdGlvbiBvZiBtYXRyaXgKICAgICAgICBpbnRbXVtdIGFkak1hdHJpeCA9IG5ldyBpbnRbXVtdCiAgICAgICAgewogICAgICAgICAgICB7IDAsICBNLCAtMiwgTSB9LAogICAgICAgICAgICB7IDQsICAwLCAgMywgTSB9LAogICAgICAgICAgICB7IE0sICBNLCAgMCwgMiB9LAogICAgICAgICAgICB7IE0sIC0xLCAgTSwgMCB9CiAgICAgICAgfTsKCiAgICAgICAgLy8gUnVuIEZsb3lkIFdhcnNoZWxsIGFsZ29yaXRobQogICAgICAgIEZsb3lkV2Fyc2hlbGwoYWRqTWF0cml4LCBOKTsKICAgIH0KfQ==