6.3 Shortest Path Routing

This is one of the simplest routing schemes.
The term shortest path does not necessarily refer to the distance between two points. The shortest path can be interpreted as (Osterloh 2002, Banerjee 2004):

Path of the least geographical distance,

Path of the least congestion,

Path of the least number of Hops,

Path of the least mean queuing delay,

Path of the least propagation / transmission delay,

The port with the most bandwidth,

The cable that has the least amount of interference,

The cheapest port to operate (as opposed to a leased line), or

A combination of 2 or more of these factors.

6.3 Shortest Path Routing

a. Dijkstra’s Algorithm
Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) (Cormen 2001). Dijkstra's algorithm is faster than the Bellman-Ford algorithm. Bellman-Ford algorithm solves the single-source shortest-path problem in the general case. In this case the edges of a given digraph can have negative weight and produce a correct answer as long as no negative-weight cycles are reachable from the source. Like Dijkstra's algorithm, this algorithm uses the notion of edge relaxation but does not use with greedy method (Cormen 2001).
Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ϵV – S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values. Figure 1 show an example for Dijkstra’s algorithm in steps.

DIJKSTRA(G, w, s)

1. INITIALIZE-SINGLE-SOURCE(G, s)
2. S ← Ø
3. Q ← V[G]
4. while Q ≠ Ø
5. do u ← EXTRACT-MIN(Q)
6. S ← S _{u}
7. for each vertex v _ Adj[u]
8. do RELAX(u, v, w)

6.3 Shortest Path Routing

Figure 1: Dijkstra Example (VEERAVAGU AND BARRERA 2011)