<< NL_R_DijkstraMapSourcesN NL_R: Routing NL_R_DijkstraNiNj >>

NARVAL >> NL_R: Routing > NL_R_DijkstraMultiPath

NL_R_DijkstraMultiPath

Perform five alternative routing tables of a network from successive applications of the Dijkstra's algorithm on a changing topology.

Calling Sequence

[P,Rt1,Rt2,Rt3,Rt4,Rt5] = NL_R_DijkstraMultiPath(G,W,N)

Arguments

G :

Graph.

W :

Weight.

N :

Storage file name.

P :

Presence table.

:

First routing table.

:

Second routing table.

:

Third routing table.

:

Fourth routing table.

:

Fifth routing table.

Description

NL_R_DijkstraMultiPath performs the five alternative routing tables , , , , and of the initial network G from successive applications of the Dijkstra's algorithm on a changing topology (WIKIPEDIA). Thus after each shortest path calculation on the current graph G, the constant weight W is added to each path link. Thereafter the Dijkstra's algorithm is executed again on the new topology and so on. n is the network size. The shortest path between the nodes ni and nj is stored into the line (ni-1)*n+nj and that for each routing table. Each routing table follows the structure [path hop length|path length|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

[path]=NL_F_NLPath();//path to NARVAL module
path=path+'/demos/';//folder path
load(path+'topo_30.graph');//loading of the network graph
w=1000;//weight
name='multitable_topo_30.dat';//backup file name
[pt,rt1,rt2,rt3,rt4,rt5]=NL_R_DijkstraMultiPath(g,w,name);//application of NL_R_DijkstraMultiPath
pt(1:10,:)
rt1(1:10,:)
rt2(1:10,:)
rt3(1:10,:)
rt4(1:10,:)
rt5(1:10,:)

Dependency

NL_R_DijkstraNiNj, NL_G_Nodes2Path, NL_F_ReverseVector, NL_R_PathWeightChange, NL_F_DiffVect, NL_R_RTReduction, NL_R_RTPathPresence

Report an issue
<< NL_R_DijkstraMapSourcesN NL_R: Routing NL_R_DijkstraNiNj >>