Routing Tables
Use the API to generate routing tables when the next-hop edges from a vertex to destination nodes will be needed later.
Routing Table for Single Source (1–>All)
Problem
Generate a routing table for a single source that contains the information on the first hop from that source node to every other destination.
The single-source routing table information is not sufficient to find a complete path between the source and any destination. The information can only be used to get a set of next-hop edges that would be used in routes from the source to a destination. Each next-hop edge represents the first hop of a complete lowest-cost path to the destination.
This is most efficiently solved by first computing the routing table for the source node and then retrieving the next hops to each destination one by one.
Usage guide
prg_djk_single_source_compute()— Compute the shortest paths between a single source and all destinations. Use this information to construct the routing table on the source node.prg_djk_next_hops_get()— Retrieve the set of outgoing edges that are first hops of lowest-cost paths to the destination.
If only the next hops to a few destinations are needed (and not the complete routing table), it might be more efficient to use the single-pair method for each (src,dest) pair, retrieving the first hop in each path from the pair’s shortest-path vector.
For example, one study on an example network showed that the break-even point in a sample 100-node network occurred when finding the next hops from a single source to 12 destinations. A rule of thumb: to find the next hops from a source to more than 10% of the destinations, use this prg_djk_single_source_compute() approach.
Routing Tables for All Sources (All–>All)
Problem
Compute the routing tables for all nodes and retrieve the next hops information from each source to each destination.
Usage guide
prg_djk_all_sources_compute()— Compute the routing table for every vertex in the graph and store this as state information on each vertex in the graph.prg_djk_next_hops_get()— Retrieve the set of next hops between a source and a destination from the state information stored on the source vertex.