<< NL_R_DFSWeightPlot NL_R: Routing NL_R_DijkstraHT >>

NARVAL >> NL_R: Routing > NL_R_Dijkstra

NL_R_Dijkstra

Perform the Dijktra's algorithm from a source on a topology.

Calling Sequence

[D,P] = NL_R_Dijkstra(G,I)

Arguments

G :

Graph.

I :

Source node.

D :

Vector of the total distance between each network node and the source node.

P :

Vector composed by the predecessor of each node in order to reach the source node in respect with the shortest path.

Description

NL_R_Dijkstra computes the shortest paths between all network nodes of the graph G towards the single source I in respect with the Dijkstra's algorithm (WIKIPEDIA). The graph is assumed to be weighted. The 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. The vector D of size N provides the total distance between each network node and the source node I. The vector P of size N gives the predecessor node of each network vertex in order to reach the source node according the shortest path.

Pseudo-Code (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[]

Examples

n=80;//network size
L=1000;//network square area side
dmax=100;//locality radius
[g]=NL_T_LocalityConnex(n,L,dmax);//generation of a random topology in respect with the Locality method. 
i=NL_F_RandInt1n(length(g.node_x));//selection of the source node
ind=1;//window index
g.node_diam(i)=40;//node diameter
g.node_border(i)=10;//node border
g.node_color(i)=5;//node color
[f]=NL_G_ShowGraphN(g,ind);//graph visualization
[dist,pred]=NL_R_Dijkstra(g,i);//application of NL_R_Dijkstra
i
dist(1:10)//first ten values
pred(1:10)//first ten values

Dependency

NL_F_RemoveFirstOcc, NL_G_NodeNeighbors, NL_G_Nodes2Path

Report an issue
<< NL_R_DFSWeightPlot NL_R: Routing NL_R_DijkstraHT >>