Abstract
The topic of shortest path algorithms is very fundamental and important in information science and technology. Shortest path algorithms have evolved over many years and have found applications in different domains such as telecommunication networks, military, and transportation. There has been a lot of work undertaken on this topic in this area in the past. A lot of research is still being conducted. The topic is still poorly understood. This article should be helpful to readers, because it reviews some of the important works conducted in the area, out of the plenty of works available on this topic. The problem is so fundamental that whatever the interest areas of the readers may be, they will find the article useful. The popular traditional shortest path algorithms date back to 1958/1959 and were proposed by Dijkstra (1959), and Bellman (1958). Their algorithms found wide applications in the abovementioned domains for many years. However, they were static. Thereafter, many other algorithms were proposed in the last few decades, all of which can be classified to be either dynamic or semi-dynamic.
TopSingle-Source Shortest Path Routing: Dynamic Versus Static
The problem of computing and maintaining information about the shortest paths information in a graph (with a single source)—where the edges are inserted/deleted and edge-weights constantly increase/decrease—is referred to as the dynamic single source shortest path problem (DSSSP). Although this problem is important, it has received little attention in the literature. The importance of the problem lies in the fact that it is representative of many practical situations in daily life, where most environments are dynamically changing. In such environments, one needs to devise efficient solutions to maintain the shortest path even though there are updates on the structure of the graph by virtue of edge-insertion/deletion, or edge-weight increase/decrease, and hopefully this can be achieved without recomputing everything “from scratch” following each topology update. An example of a single-source shortest path graph, after the insertion of an edge is shown in Figure 1. The new edge C→F appears in the list of shortest paths, and the existing edge B→F, which was earlier in the list of shortest paths, ceases to be so.
Figure 1. Graph after the insertion of the edge C→F with weight 0.5
Out of the four possible edge operations (insertion/deletion and increase/decrease), it has been shown that edge-insertion is equivalent to edge-weight decrease, and edge-deletion is equivalent to edge-weight increase. Increasing or decreasing an edge-weight can be performed by inserting a new edge (with the new weight) parallel to the edge under consideration, and then deleting the old edge (Ramalingam & Reps, 1996). If all edge operations are allowed, the problem is referred to as the fully dynamic problem. If only edge-insertion/weight-decrease (or edge-deletion/weight-increase) is allowed, the problem is referred to as the semi-dynamic problem (Frigioni, Marchetti-Spaccamela, & Nanni, 1996).
Key Terms in this Chapter
Semi-Dynamic Shortest Path Algorithm: If in a dynamic shortest-path algorithm, only edge-insertion/weight-decrease, or edge-deletion/weight-increase is allowed, the algorithm is referred to as the semi-dynamic algorithm.
Algorithm: An algorithm is a set of clear steps that is used to define how a task or a set of tasks can be accomplished.
Routing: The mechanism by which a path or a set of paths is selected to send information or commodities.
Static Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network, when all the nodes and links remain stationary.
Dynamic Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network, when the status of nodes and links change with time.
Shortest Path Algorithm: An algorithm that is capable of finding a path that has the least distance (among all possible paths) between a pair of source and destination nodes in a network.
Fully Dynamic All-Pairs Shortest Path Algorithm: If in a dynamic shortest-path algorithm, all edge operations (edge-insertion, weight-decrease, edge-deletion, weight-increase) are allowed, the algorithm is referred to as the fully dynamic algorithm.