<< NARVAL_R_FloodIteration NARVAL NARVAL_R_FloydWarshallP >>

NARVAL >> NARVAL > NARVAL_R_FloydWarshall

NARVAL_R_FloydWarshall

Perform all shortest paths between all pairs of vertices of a graph in respect with the Floyd-Warshall algorithm.

Calling Sequence

[Path,Next]=NARVAL_R_FloydWarshall(g)

Parameters

g :

network graph.

Path :

matrix of path length between two network nodes.

Next :

matrix of successor nodes.

Description

NARVAL_R_FloydWarshall 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.

Pseudo-Code (Wikipedia)

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..k1).  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] );

Examples

[path]=NARVAL_F_NARVALPath();//path to NARVAL module
path=path+'/demos/';//folder path
load(path+'topo_100.graph');//loading of the network graph
load(path+'RoutingTables_topo_100.dat','pt','rt1','rt2','rt3','rt4','rt5');//loading of the network routing tables
[Path,Next]=NARVAL_R_FloydWarshall(g);//Application of NARVAL_R_FloydWarshall
Path(1:10,1:10)
Next(1:10,1:10)

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact

<< NARVAL_R_FloodIteration NARVAL NARVAL_R_FloydWarshallP >>