<< NARVAL_R_DFSWWD NARVAL NARVAL_R_Dijkstra_i_j >>

NARVAL >> NARVAL > NARVAL_R_Dijkstra

NARVAL_R_Dijkstra

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

Calling Sequence

[d,p] = NARVAL_R_Dijkstra(g,i)

Parameters

g :

network graph.

i :

source node.

d :

vector of the total distance between each network node and the source node i.

p :

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

Description

NARVAL_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]=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
g.node_diam(i)=40;//node diameter
g.node_border(i)=10;//node border
g.node_color(i)=5;//node color
[f]=NARVAL_G_ShowNodesIndex(g,ind);//graph visualization
[dist,pred]=NARVAL_R_Dijkstra(g,i);//application of NARVAL_R_Dijkstra
i
dist(1:10)//first ten values
pred(1:10)//first ten values

Dependency

NARVAL_F_Remov, NARVAL_G_NodeNeighbors, NARVAL_G_Nodes2Path

Authors

Foued Melakessou

Contact

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

Home Page


<< NARVAL_R_DFSWWD NARVAL NARVAL_R_Dijkstra_i_j >>