23 lines
743 B
Plaintext
23 lines
743 B
Plaintext
fcn FloydWarshallWithPathReconstruction(dist){ // dist is munged
|
|
V:=dist[0].len();
|
|
next:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void
|
|
foreach u,v in (V,V){ if(dist[u][v]!=Void and u!=v) next[u][v] = v }
|
|
foreach k,i,j in (V,V,V){
|
|
a,b,c:=dist[i][j],dist[i][k],dist[k][j];
|
|
if( (a!=Void and b!=Void and c!=Void and a>b+c) or // Inf math
|
|
(a==Void and b!=Void and c!=Void) ){
|
|
dist[i][j] = b+c;
|
|
next[i][j] = next[i][k];
|
|
}
|
|
}
|
|
return(dist,next)
|
|
}
|
|
fcn path(next,u,v){
|
|
if(Void==next[u][v]) return(T);
|
|
path:=List(u);
|
|
while(u!=v){ path.append(u = next[u][v]) }
|
|
path
|
|
}
|
|
fcn printM(m){ m.pump(Console.println,rowFmt) }
|
|
fcn rowFmt(row){ ("%5s "*row.len()).fmt(row.xplode()) }
|