Sudip Misra (Cornell University, USA)

Copyright: © 2009
|Pages: 5

DOI: 10.4018/978-1-60566-026-4.ch548

Chapter Preview

TopThe 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.

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).

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.

Search this Book:

Reset

Copyright © 1988-2019, IGI Global - All Rights Reserved