Perform the Dijkstra's algorithm on a network topology from a source node in respect with given links weights (shortest path to all remaining nodes).
[d,p] = NARVAL_M_DijkstraWeight(n,h,t,w,nd)
network size.
links head vector.
links tail vector.
links weight vector.
source node.
distance vector from the source node towards remaining network nodes.
predecessors vector to reach the source node from remaining network nodes.
NARVAL_M_DijkstraWeight performs the Dijkstra's algorithm from the source node nd on the network topology represented by the 3 following vectors: h, t and w. Links weights are provided by the user. d and p enable to reconstruct the shortest path between any network node towards the source node ni (WIKIPEDIA).
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[] | ![]() | ![]() |
n=80;//network size L=1000;//network square area side dmax=100;//locality radius [g]=NARVAL_T_LocalityConnex(n,L,dmax);//generation of a random topology in respect with the Locality method. i=NARVAL_F_Random(length(g.node_x));//selection of the source node ind=1;//window index f=NARVAL_G_ShowNodesIndex(g,ind); [dist,pred]=NARVAL_M_DijkstraWeight(g.node_number,g.head,g.tail,g.edge_length,i);//Application of NARVAL_M_DijkstraWeight i dist pred | ![]() | ![]() |
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