Perform the routing table of a topology in respect with the Bellman-Ford algorithm.
[rt] = NARVAL_R_TBellmanFord(g)
network graph.
routing table.
NARVAL_R_TBellmanFord computes the shortest paths between all couples of distinct network nodes of the graph g composed by n nodes in respect with the Bellman-Ford algorithm (WIKIPEDIA). The paths are stored in the routing table matrix rt. Thus the route between the nodes i and j can be read at the line of index (i-1)*n+j. The first column of rt provides each path length.
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" | ![]() | ![]() |
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