Perform the routing table of a topology in respect with the Bellman-Ford algorithm.
[rt]=RoutingTableBellmanFord(g)
network graph.
routing table.
RoutingTableBellmanFord computes the shortest paths between all couples of distinct network nodes of the graph g in respect with the Bellman-Ford algorithm. They 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 where n represents the network size. 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" | ![]() | ![]() |