<< RoutingBFSWeight Network Topology Generator RoutingCongestionMap >>

Network Topology Generator >> Network Topology Generator > RoutingBellmanFord

RoutingBellmanFord

Perform the Bellman-Ford algorithm from a source node on a topology.

Calling Sequence

[dist,pred]=RoutingBellmanFord(g,i)

Parameters

g :

network graph.

i :

source node.

dist :

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

pred :

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

Description

RoutingBellmanFord computes the shortest paths between all network nodes of the graph g towards a single source i in respect with the Bellman-Ford algorithm. The graph is assumed to be weighted. Edge weights may be negative. All graph edges are relaxed, and that n-1 times, where n corresponds to the network size. The iterations propagate minimum distances throughout the graph. dist is a vector of size n that provides the total distance between each network node and the source node i. pred represents also a vector of size n that gives the predecessor node of each network vertex in order to reach the source node according the shortest path.

Pseudo-Code (Wikipedia)

procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: Initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null
   
   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:       
       for each edge uv in edges: // uv is the edge from u to v
           u := uv.source
           v := uv.destination             
           if u.distance + uv.weight is inferior to v.distance:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight is inferior to v.distance:
           error "Graph contains a negative-weight cycle"

Examples

n=80;//network size
L=1000;//network square area side
dmax=100;//locality radius
[g]=NtgLocalityConnex(n,L,dmax);//generation of a random topology in respect with the Locality method. 
i=Random(length(g.node_x));//selection of the source node
EB=ones(1,length(g.node_x));//display the source node
EC=ones(1,length(g.node_x));
EB(i)=3;
EC(i)=5;
g.node_border=EB;
g.node_color=EC;
show_graph(g);
[dist,pred]=RoutingBellmanFord(g,i);//Application of RoutingBellmanFord
i
dist
pred

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact


<< RoutingBFSWeight Network Topology Generator RoutingCongestionMap >>