Internet Routing with Dijkstra’s Algorithm (BGL Book Chapter 5.4)

Based on “The Boost Graph Library” by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine

Overview

An important application of shortest-path algorithms is Internet packet routing. The protocols that control how packets of information are transmitted through the Internet use shortest-path algorithms to reduce the amount of time it takes for a packet to reach its destination.

When a computer sends a message to another using the Internet Protocol (IP), the message contents are put into a packet. If the destination address for the packet is outside of the local network, the packet will be sent from the originating machine to an Internet router. The router directs packets that it receives to other routers based on its routing table.

Dijkstra’s Algorithm

Dijkstra’s algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively growing the set of vertices S to which it knows the shortest path. At each step of the algorithm:

  1. The vertex in V - S with the smallest distance label is added to S

  2. The out-edges of the vertex are relaxed: d[v] = min(w(u,v) + d[u], d[v])

  3. The algorithm loops back, processing the next vertex with the lowest distance label

The algorithm finishes when S contains all vertices reachable from the source vertex.

Key difference from Bellman-Ford: Dijkstra’s algorithm requires non-negative edge weights but is more efficient: O((V+E) log V) versus O(V*E) for Bellman-Ford.

NWGraph Implementation

NWGraph provides a dijkstra function that implements Dijkstra’s algorithm using modern C++20 features.

Listing 4 Complete source code
 1/**
 2 * @file ch5_dijkstra.cpp
 3 *
 4 * @brief Internet Routing with Dijkstra's Algorithm (BGL Book Chapter 5.4)
 5 *
 6 * This example demonstrates Dijkstra's single-source shortest-paths algorithm
 7 * using an OSPF (Open Shortest Path First) router network graph. OSPF is a
 8 * link-state routing protocol where each router maintains a complete topology
 9 * of the network and computes shortest paths using Dijkstra's algorithm.
10 *
11 * @copyright SPDX-FileCopyrightText: 2022 Battelle Memorial Institute
12 * @copyright SPDX-FileCopyrightText: 2022 University of Washington
13 *
14 * SPDX-License-Identifier: BSD-3-Clause
15 *
16 * @authors
17 *   Andrew Lumsdaine
18 *
19 */
20
21#include <iostream>
22#include <limits>
23#include <vector>
24
25#include "nwgraph/adjacency.hpp"
26#include "nwgraph/algorithms/dijkstra.hpp"
27#include "nwgraph/edge_list.hpp"
28#include "nwgraph/graphs/ospf-graph.hpp"
29
30using namespace nw::graph;
31
32int main() {
33  std::cout << "=== Internet Routing with Dijkstra's Algorithm ===" << std::endl;
34  std::cout << "Based on BGL Book Chapter 5.4" << std::endl << std::endl;
35
36  // Build the graph from the OSPF edge list data
37  // The OSPF graph represents a network topology with routers (RT) and networks (N)
38  size_t num_vertices = ospf_vertices.size();
39
40  std::cout << "Network topology has " << num_vertices << " nodes:" << std::endl;
41  std::cout << "  Routers: RT1-RT12" << std::endl;
42  std::cout << "  Networks: N1-N15" << std::endl;
43  std::cout << "  Host: H1" << std::endl << std::endl;
44
45  // Create edge list from the OSPF index edge list
46  edge_list<directedness::directed, size_t> edges(num_vertices);
47  edges.open_for_push_back();
48  for (auto&& [u, v, w] : ospf_index_edge_list) {
49    edges.push_back(u, v, w);
50  }
51  edges.close_for_push_back();
52
53  // Build adjacency representation
54  adjacency<0, size_t> G(edges);
55
56  // Run Dijkstra from RT6 (vertex 5) - this is what the BGL book example uses
57  size_t source = 5;  // RT6
58  std::cout << "Computing shortest paths from " << ospf_vertices[source] << "..." << std::endl;
59  std::cout << std::endl;
60
61  auto distance = dijkstra<size_t>(G, source);
62
63  // Display results
64  std::cout << "Shortest path distances from " << ospf_vertices[source] << ":" << std::endl;
65  std::cout << std::string(50, '-') << std::endl;
66
67  for (size_t i = 0; i < num_vertices; ++i) {
68    std::cout << "  " << ospf_vertices[i] << ": ";
69    if (distance[i] == std::numeric_limits<size_t>::max()) {
70      std::cout << "unreachable";
71    } else {
72      std::cout << distance[i];
73    }
74
75    // Compare with expected values from the BGL book
76    size_t expected = std::get<1>(ospf_shortest_path_distances[i]);
77    if (distance[i] != expected && distance[i] != std::numeric_limits<size_t>::max()) {
78      std::cout << " (expected: " << expected << ")";
79    }
80    std::cout << std::endl;
81  }
82
83  std::cout << std::endl;
84  std::cout << "Note: In OSPF, link costs are typically based on bandwidth." << std::endl;
85  std::cout << "Routers use these shortest paths to build their routing tables." << std::endl;
86
87  return 0;
88}

Building and Running the Example

First, configure and build the example:

# From the NWGraph root directory
mkdir -p build && cd build
cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make ch5_dijkstra

Then run the example:

./examples/bgl-book/ch5_dijkstra

The program computes shortest paths from a source router to all other routers in an OSPF-style network, demonstrating how link-state routing protocols work.

Sample Output

OSPF Router Network - Dijkstra's Shortest Paths
Source: Router 6

Router 1: distance = 8, next hop = Router 3
Router 2: distance = 5, next hop = Router 3
Router 3: distance = 2, next hop = Router 3
...

Key NWGraph Features Demonstrated

  • Weighted directed graphs: Router networks with transmission delays

  • Priority queue-based traversal: Efficient vertex selection by distance

  • Predecessor tracking: Recording the shortest-paths tree

  • Property maps: Associating distances and predecessors with vertices

References

  • Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 4th Edition (2022), Chapter 22.3: Dijkstra’s Algorithm

  • Siek, Lee, and Lumsdaine. The Boost Graph Library (2002), Chapter 5.4

See Also