2011-02-28 CLRS Chapter25 All-Pairs Shortest Paths 每对顶点间的最短路径

//打印出从顶点i到顶点j的一条最短路径，Π是前驱矩阵π_ij表示从i到顶点j的一条最短路径上j的前驱 PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j) 1  if i = j 2    then print i 3    else if π_ij = NIL 4         then print "no path from" i "to" j "exists" 5         else PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, π_ij) 6                     print j

 

The Floyd-Warshall algorithm

Transitive closure of a directed graph

Johnson's algorithm for sparse graphs