Perform the routing table of a topology in respect with the Dijkstra's algorithm.
[rt]=RoutingTableDijkstra(g)
network graph.
routing table.
RoutingTableDijkstra computes the shortest paths between all couples of distinct network nodes of the graph g in respect with the Dijkstra's 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.
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[] | ![]() | ![]() |