Perform the shortest path between two network nodes in respect with the Dijkstra's algorithm (Scilab).
[path]=RoutingDijkstra(g,typ,i,j)
network graph.
search type.
emission node.
destination node.
route between i and j.
RoutingDijkstra performs the shortest path between two nodes i and j of the graph g. typ can take the value 'arc' (in respect with the number of arcs belonging to the path) or 'length' (in respect with the path length). path corresponds to the shortest path composed by a succession of nodes between i and j.
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=150;//network size L=1000;//network square area side dmax=100;//Locality radius [g]=NtgLocalityConnex(n,L,dmax);//generation of a topology in respect with the Locality method nf=length(g.node_x);//real network size nl=length(g.head);//quantity of network links [i,j]=Random_i_j(nf);//selection of the extremal nodes [path]=RoutingDijkstra(g,'arc',i,j);//application of RoutingDijkstra p=nodes_2_path(path,g); EC=ones(1,nl);//display the path between i and j EB=ones(1,nl); EC(p)=5; EB(p)=2; D=ones(1,nf); D(path)=3; g.node_border=D; g.edge_color=EC; g.edge_width=EB; show_graph(g); path | ![]() | ![]() |