Perform the Dijktra's algorithm from a source on a topology.
[dist,pred]=RoutingDijkstraO(g,i)
network graph.
source node.
vector of the total distance between each network node and the source node i.
vector composed by the predecessor of each node in order to reach the source node in respect with the shortest path.
RoutingDijkstra0 computes the shortest paths between all network nodes of the graph g towards a single source i in respect with the Dijkstra's algorithm. The graph is assumed to be weighted. Edge weights must be positive. The graph edges of the current node neighborhood are relaxed. The displacement of the current node propagates minimum distances throughout the graph. n corresponds to the network size. dist is a vector of size n that provides the total distance between each network node and the source node i. pred represents also a vector of size n that gives the predecessor node of each network vertex in order to reach the source node according the shortest 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[] | ![]() | ![]() |
n=80;//network size L=1000;//network square area side dmax=100;//locality radius [g]=NtgLocalityConnex(n,L,dmax);//generation of a random topology in respect with the Locality method. i=Random(length(g.node_x));//selection of the source node show_graph(g); hilite_nodes(i); [dist,pred]=RoutingDijkstraO(g,i);//Application of RoutingDijkstraO i dist pred | ![]() | ![]() |