<< NARVAL_R_Dijkstra NARVAL NARVAL_R_ERoutingTable >>

NARVAL >> NARVAL > NARVAL_R_Dijkstra_i_j

NARVAL_R_Dijkstra_i_j

Perform the shortest path between two network nodes in respect with the Dijkstra's algorithm.

Calling Sequence

[path]=NARVAL_R_Dijkstra_i_j(g,i,j)

Parameters

g :

network graph.

i :

emission node.

j :

destination node.

path :

route between i and j.

Description

NARVAL_R_Dijkstra_i_j 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.

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=150;//network size
L=1000;//network square area side
dmax=100;//Locality radius
[g]=NARVAL_T_LocalityConnex(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]=NARVAL_F_Random_i_j(nf);//selection of the extremal nodes
[path]=NARVAL_R_Dijkstra_i_j(g,i,j);//application of NARVAL_R_Dijkstra_i_j
[p]=NARVAL_G_Nodes2Path(path,g);
Ebi=2;
EC=ones(1,nl);//display the path between i and j
EB=Ebi*ones(1,nl);
EC(p)=5;
EB(p)=2*Ebi;
Bdi=5;
D=Bdi*ones(1,nf);
D(path)=3*Bdi;
g.node_border=D;
g.edge_color=EC;
g.edge_width=EB;
ind=1;
[f]=NARVAL_G_ShowGraph(g,ind);
path

Dependency

NARVAL_R_Dijkstra, NARVAL_R_PredRoute

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact

<< NARVAL_R_Dijkstra NARVAL NARVAL_R_ERoutingTable >>