Perform five alternative routing tables of a network from successive applications of the Dijkstra's algorithm on a changing topology.
[pt,rt1,rt2,rt3,rt4,rt5] = NARVAL_R_MPathDijkstra(g,w,name)
network graph.
weight.
storage file name.
presence table.
first routing table.
second routing table.
third routing table.
fourth routing table.
fifth routing table.
NARVAL_R_MPathDijkstra performs the five alternative routing tables rt1, rt2, rt3, rt4, and rt5 of the initial network g from successive applications of the Dijkstra's algorithm on a changing topology (WIKIPEDIA). Thus after each shortest path calculation on the current graph g, the constant weight w is added to each path link. Thereafter the Dijkstra's algorithm is executed again on the new topology and so on. n is the network size. The shortest path between the nodes ni and nj is stored into the line (ni-1)*n+nj and that for each routing table. Each routing table follows the structure [path hop length|path length|path].
1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity // Unknown distance function from source to v 4 previous[v] := undefined // Previous node in optimal path from source 5 dist[source] := 0 // Distance from source to source 6 Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q 7 while Q is not empty: // The main loop 8 u := vertex in Q with smallest dist[] 9 if dist[u] = infinity: 10 break // all remaining vertices are inaccessible from source 11 remove u from Q 12 for each neighbor v of u: // where v has not yet been removed from Q. 13 alt := dist[u] + dist_between(u, v) 14 if alt is inferior to dist[v]: // Relax (u,v,a) 15 dist[v] := alt 16 previous[v] := u 17 return dist[] | ![]() | ![]() |
[path]=NARVAL_F_NARVALPath();//path to NARVAL module path=path+'/demos/';//folder path load(path+'topo_30.graph');//loading of the network graph w=1000;//weight name='multitable_topo_30.dat';//backup file name [pt,rt1,rt2,rt3,rt4,rt5]=NARVAL_R_MPathDijkstra(g,w,name);//application of RoutingMPathDijkstra pt(1:10,:) rt1(1:10,:) rt2(1:10,:) rt3(1:10,:) rt4(1:10,:) rt5(1:10,:) | ![]() | ![]() |
Dr. Foued Melakessou
Research Associate
Interdisciplinary Centre for Security, Reliability and Trust
Room F106
University of Luxembourg
6, rue Coudenhove Kalergi
L-1359 Luxembourg-Kirchberg
E-mail: foued.melakessou@uni.lu
Tel: (+352) 46 66 44 5346