Perform all shortest paths between all pairs of vertices of a graph in respect with the Floyd-Warshall algorithm.
[Path,Next]=RoutingFloydWarshall(g)
network graph.
matrix of path length between two network nodes.
matrix of successor nodes.
RoutingFloydWarshall finds the shortest paths between all pairs of vertices of the graph g of n nodes in a single execution. Routes can be retrieved according to two matrices of size nxn. Path(i,j) provides the total length of the shortest path between the nodes i and j. Next(i,j) provides an intermediate node that should be crossed in order to reach j from i in respect with the shortest path.
1 /* Assume a function edgeCost(i, j) which returns the cost of the edge from i to j 2 (infinity if there is none). 3 Also assume that n is the number of vertices and edgeCost(i,i) = 0 4 */ 5 6 int path[][]; 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 8 from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to 9 edgeCost(i,j) or infinity if there is no edge between i and j. 10 */ 11 12 procedure FloydWarshall () 13 for k := 1 to n 14 for i := 1 to n 15 for j := 1 to n 16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] ); | ![]() | ![]() |
load('./demos/RoutingTables_topo_100_1.dat');//loading of the network routing tables g=load_graph('./demos/topo_100_1.graph');//loading of the network graph [g]=EdgeLength(g); [Path,Next]=RoutingFloydWarshall(g);//Application of RoutingFloydWarshall Path(1:10,1:10) Next(1:10,1:10) | ![]() | ![]() |