IP Routing

Definitions and Concepts

Dijkstra’s algorithm solves the problem of discovering the shortest path from a single source to all vertices in a graph where the edges are each represented with a cost. For example, a car driver could use Dijkstra’s algorithm to find the shortest paths from New York to major cities in the northeastern U.S. and Canada. The input to Dijkstra would be a graph that could be represented by a matrix like that shown in Table 6-2.

Table 6-2. Driving distances

Town name	Town name	Driving distance (miles)
New York	Washington	236
New York	Boston	194
Boston	Chicago	996
Washington	Chicago	701
New York	Toronto	496
Detroit	Chicago	288
Washington	Detroit	527
Boston	Toronto	555
Toronto	Detroit	292

The output would be the shortest paths from New York to all other cities in the graph. A geographical view of Table 6-2 is contained in Figure 6-3.

Figure 6-3. Geographical view of driving distances

There are six nodes in this graph: New York, Chicago, Boston, Toronto, Detroit, and Washington. There are nine edges in the graph, each represented by the distance between a pair of vertices. The SPF algorithm works as follows:

1. Starting at the source node -- New York -- build a list of one-segment paths originating at the source node. This list will be New York → Washington, New York → Boston, and New York → Toronto.

2. Sort this list in increasing order. The ...