Chapter 4 New multiple pairs shortest paths algorithms

[pdf:326kB] [ps:617kB]

        We have reviewed most of the shortest path algorithms in the literature in Chapter 3. Our purpose is to design new algorithms that can efficiently solve the MPSP problem. In this Chapter, we propose two new MPSP algorithms that exploit ideas from Carré's APSP algorithm (see Section 3.4.1.1).
Section 4.1 introduces some definitions and basic concepts. Section 4.2 presents our first new MPSP algorithm (DLU1) and proves its correctness. Section 4.3 gives our second algorithm (DLU2) and describes why it is superior to the first one. Section 4.4 summarize our work.

Summary

        In this chapter we propose two new algorithms called DLU1 and DLU2 that are suitable for solving MPSP problems. Although their worst case complexity O(n³) is no more efficient than other algebraic APSP algorithms such as Floyd-Warshall <cite>Fl62, Wa62</cite> and Carré's <cite>Ca69, Ca71</cite> algorithms, our algorithms can, in practice, avoid significant computational work in solving MPSP problems.

        First obtaining the shortest distances from or to the last node n, algorithm DLU1(i0,j0,k0) systematically obtains shortest distances for all node pairs (s,t) such that s=k0, t=j0 or s=i0, t=k0 where k0:=min_{i}{max{s_{i},t_{i}}}. By setting i0:=1, it can be used to build the shortest path trees rooted at each node t=k0. When solving MPSP problems, this algorithm may be sensitive to the distribution of requested OD pairs and the node ordering. In particular, when the requested OD pairs are closely distributed in the right lower part of the n×n OD matrix, algorithm DLU1 can terminate much earlier. On the other hand, scattered OD pairs might make the algorithm less efficient, although it will still be better than other APSP algorithms. A bad node ordering may require many "fill-ins." These fill-ins make the modified graph denser, which in turn will require more triple comparisons when applying our algorithms. Such difficulties may be resolved by reordering the node indices so that the requested OD pairs are grouped in a favorable distribution and/or the required number of fill-in arcs is decreased.

        Algorithm DLU2 attacks each requested OD pair individually, so it is more suitable for problems with a scattered OD distribution. It also overcomes the computational inefficiency that algorithm DLU1 has in tracing shortest paths. It is especially efficient for solving a special MPSP problem of n OD pairs (s_{i},t_{i}) that correspond to a matching. That is, each node appears exactly once in the source and sink node set but not the same time. Such an MPSP problem requires as much work as an APSP problem using most of the shortest path algorithms known nowadays, even though only n OD pairs are requested.
Our algorithms (especially DLU2) are advantageous when only the shortest distances between some OD pairs are required. For a graph with fixed topology, or a problem with fixed requested OD pairs where shortest paths have to be repeatedly computed with different numerical values of arc lengths, our algorithms are especially beneficial since we may do a preprocessing step in the beginning to arrange a good node ordering that favors our algorithms. These problems appear often in real world applications. For example, when solving the origin-destination multicommodity network flow problem (ODMCNF) using Dantzig-Wolfe decomposition and column generation <cite>BaJoHaSi95</cite>, we generate columns by solving sequences of shortest path problems between some fixed OD pairs where the arc cost changes in each stage but the topology and requested OD pairs are both fixed. Also, in the computation of parametric shortest paths where arc length is a linear function of some parameter, we may solve shortest distances iteratively on the same graph to determine the critical value of the parameter.

        Our algorithms can deal with graphs containing negative arc lengths and detect negative cycles as well. The algorithms save storage and computational work for problems with special structures such as undirected or acyclic graphs.

        Although we have shown the superiority of our algorithms over other algebraic APSP algorithms, it is, however, still not clear how our algorithms perform when they are compared with modern SSSP algorithms empirically. Like all other algebraic algorithms in the literature, our algorithms require O(n²) storage which makes them more suitable for dense graphs. We introduced techniques of sparse implementation that avoid nontrivial triple comparisons, but they come with the price of extra storage for the adjacency data structures.

        A more thorough computational experiment to compare the empirical efficiency of DLU1 and DLU2 with many modern SSSP and APSP algorithms is conducted in Chapter 5, in which we introduce additional sparse implementation techniques that lead to promising computational results.