<< RoutingDFSWeight Network Topology Generator RoutingDijkstra0 >>

Network Topology Generator >> Network Topology Generator > RoutingDijkstra

RoutingDijkstra

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

Calling Sequence

[path]=RoutingDijkstra(g,typ,i,j)

Parameters

g :

network graph.

typ :

search type.

i :

emission node.

j :

destination node.

path :

route between i and j.

Description

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.

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]=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

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact


<< RoutingDFSWeight Network Topology Generator RoutingDijkstra0 >>