Perform the routing table of a topology in respect with the Dijkstra's algorithm.
[R] = NL_R_DijkstraRT(G)
Graph.
Routing table.
NL_R_DijkstraRT computes the shortest paths between all couples of distinct network nodes of the graph G composed by n nodes in respect with the Dijkstra's algorithm (WIKIPEDIA). The paths are stored in the routing table matrix R. 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 R 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[] | ![]() | ![]() |