import Ġjava . util .* Ċ Ċ class ĠF loy d Ġ{ ĊĊĠĠĠ Ġfun Ġshortest path ( adj : ĠArray < IntArray >, Ġpath : ĠArray < IntArray >): ĠArray < IntArray > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġadj . size ĊĠĠĠĠĠĠĠ Ġval Ġans Ġ= ĠArray ( n ) Ġ{ ĠInt Array ( n ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠImplement Ġalgorithm Ġon Ġa Ġcopy Ġmatrix Ġso Ġthat Ġthe Ġad jacency Ġisn 't ĊĠĠĠĠĠĠĠ Ġ// Ġdestroyed . ĊĠĠĠĠĠĠĠ Ġcopy ( ans , Ġadj ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠCompute Ġsuccess ively Ġbetter Ġpaths Ġthrough Ġvertex Ġk . ĊĠĠĠĠĠĠĠ Ġfor Ġ( k Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠDo Ġso Ġbetween Ġeach Ġpossible Ġpair Ġof Ġpoints . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ans [ i ][ k ] Ġ+ Ġans [ k ][ j ] Ġ< Ġans [ i ][ j ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġans [ i ][ j ] Ġ= Ġans [ i ][ k ] Ġ+ Ġans [ k ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath [ i ][ j ] Ġ= Ġpath [ k ][ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠReturn Ġthe Ġshortest Ġpath Ġmatrix . ĊĠĠĠĠĠĠĠ Ġreturn Ġans ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠCop ies Ġthe Ġcontents Ġof Ġarray Ġb Ġinto Ġarray Ġa . ĠAss umes Ġthat Ġboth Ġa Ġand ĊĠĠĠ Ġ// Ġb Ġare Ġ 2 D Ġarrays Ġof Ġidentical Ġdimensions . ĊĠĠĠ Ġfun Ġcopy ( a : ĠArray < IntArray >, Ġb : ĠArray < IntArray >) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġa . indices ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġa [ 0 ]. size ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa [ i ][ j ] Ġ= Ġb [ i ][ j ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠReturns Ġthe Ġsmaller Ġof Ġa Ġand Ġb . ĊĠĠĠ Ġfun Ġmin ( a : ĠInt , Ġb : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( a Ġ< Ġb ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa ĊĠĠĠĠĠĠĠ Ġelse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġstdin Ġ= ĠScanner ( System .` in `) ĊĊĊĠĠĠĠĠĠĠ Ġ// ĠTests Ġout Ġalgorithm Ġwith Ġgraph Ġshown Ġin Ġclass . ĊĠĠĠĠĠĠĠ Ġval Ġm Ġ= ĠArray ( 5 ) Ġ{ ĠInt Array ( 5 ) Ġ} ĊĠĠĠĠĠĠĠ Ġm [ 0 ][ 0 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġm [ 0 ][ 1 ] Ġ= Ġ 3 ĊĠĠĠĠĠĠĠ Ġm [ 0 ][ 2 ] Ġ= Ġ 8 ĊĠĠĠĠĠĠĠ Ġm [ 0 ][ 3 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 0 ][ 4 ] Ġ= Ġ- 4 ĊĠĠĠĠĠĠĠ Ġm [ 1 ][ 0 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 1 ][ 1 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġm [ 1 ][ 2 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 1 ][ 3 ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġm [ 1 ][ 4 ] Ġ= Ġ 7 ĊĠĠĠĠĠĠĠ Ġm [ 2 ][ 0 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 2 ][ 1 ] Ġ= Ġ 4 ĊĠĠĠĠĠĠĠ Ġm [ 2 ][ 2 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġm [ 2 ][ 3 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 2 ][ 4 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 3 ][ 0 ] Ġ= Ġ 2 ĊĠĠĠĠĠĠĠ Ġm [ 3 ][ 1 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 3 ][ 2 ] Ġ= Ġ- 5 ĊĠĠĠĠĠĠĠ Ġm [ 3 ][ 3 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġm [ 3 ][ 4 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 4 ][ 0 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 4 ][ 1 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 4 ][ 2 ] Ġ= Ġ 1 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġm [ 4 ][ 3 ] Ġ= Ġ 6 ĊĠĠĠĠĠĠĠ Ġm [ 4 ][ 4 ] Ġ= Ġ 0 ĊĊĊĠĠĠĠĠĠĠ Ġval Ġshort path : ĠArray < IntArray > ĊĠĠĠĠĠĠĠ Ġval Ġpath Ġ= ĠArray ( 5 ) Ġ{ ĠInt Array ( 5 ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠInitialize Ġwith Ġthe Ġprevious Ġvertex Ġfor Ġeach Ġedge . Ġ- 1 Ġindicates ĊĠĠĠĠĠĠĠ Ġ// Ġno Ġsuch Ġvertex . ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 .. 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( m [ i ][ j ] Ġ== Ġ 1 0 0 0 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath [ i ][ j ] Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath [ i ][ j ] Ġ= Ġi ĊĊĠĠĠĠĠĠĠ Ġ// ĠThis Ġmeans Ġthat Ġwe Ġdon 't Ġhave Ġto Ġgo Ġanywhere Ġto Ġgo Ġfrom Ġi Ġto Ġi . ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath [ i ][ i ] Ġ= Ġi ĊĊĊĠĠĠĠĠĠĠ Ġshort path Ġ= Ġshortest path ( m , Ġpath ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠPrints Ġout Ġshortest Ġdistances . ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 .. 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . out . print ( short path [ i ][ j ]. toString () Ġ+ Ġ" Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . out . println () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ ĠSystem . out . println (" From Ġwhere Ġto Ġwhere Ġdo Ġyou Ġwant Ġto Ġfind Ġthe Ġshortest Ġpath ?( 0 Ġto Ġ 4 )") ĊĠĠĠĠĠĠĠ Ġval Ġstart Ġ= Ġstdin . nextInt () ĊĠĠĠĠĠĠĠ Ġvar Ġend Ġ= Ġstdin . nextInt () ĊĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġpath Ġwill Ġalways Ġend Ġat Ġend . ĊĠĠĠĠĠĠĠ Ġvar Ġmy Path Ġ= Ġend Ġ+ Ġ"" ĊĊĠĠĠĠĠĠĠ Ġ// ĠLoop Ġthrough Ġeach Ġprevious Ġvertex Ġuntil Ġyou Ġget Ġback Ġto Ġstart . ĊĠĠĠĠĠĠĠ Ġwhile Ġ( path [ start ][ end ] Ġ!= Ġstart ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmy Path Ġ= Ġpath [ start ][ end ]. toString () Ġ+ Ġ" Ġ-> Ġ" Ġ+ Ġmy Path ĊĠĠĠĠĠĠĠĠĠĠĠ Ġend Ġ= Ġpath [ start ][ end ] ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠJust Ġadd Ġstart Ġto Ġour Ġstring Ġand Ġprint . ĊĠĠĠĠĠĠĠ Ġmy Path Ġ= Ġstart Ġ+ Ġ" Ġ-> Ġ" Ġ+ Ġmy Path ĊĠĠĠĠĠĠĠ ĠSystem . out . println (" Here 's Ġthe Ġpath Ġ$ my Path ") ĊĊĠĠĠ Ġ} Ċ }