We provide a number of modules for the solution of a variety of shortest path problems. You are welcome to use them. The list of modules is provided below. You should bear in mind though that these modules are educationally oriented so .... do not expect to find here facilities for the solution of large scale shortest path problems.
For the benefit of visitors who are not familiar with this problem and the important role it plays in applied mathematics, computer science and artificial intelligence, we also provide below a very brief overview.
It is safe to say that the shortest path problem is one of the most important generic problems in such fields as operations research (OR), computer science (CS) and and artificial intelligence (AI). One of the reasons for this is that essentially any combinatorial optimization problem can be formulated as a shortest path problem. Thus, this class of problems is extremely large and includes numerous practical problems that have nothing to do with actual ("genuine") shortest path problems.
New classes of genuine shortest path problem are becoming very important these days in connection with practical applications of Geographic Information Systems (GIS) such as on line computing of driving directions. It is not surprising therefore that, for example, Microsoft has a research project on algorithms for shortest path problems.
What may surprise a bit our students is how late in the history of applied mathematics this generic problem became the topic of extensive research work that ultimately produced efficient solution methods. However, in many respects it is not an accident at all that this generic problem is so intimately connected to the early days of OR/MS and electronic computers. The following quote is very indicative (Moore [1959, p. 292]):
The problem was first solved in connection with Claude Shannon's maze-solving machine. When this machine was used with a maze which had more than one solution, a visitor asked why it had not built to always find the shortest path. Shannon and I each attempted to find economical methods of doing this by machine. He found several methods suitable for analog computation, and I obtained these algorithms. Months later the applicability of these ideas to practical problems in communication and transportation systems was suggested. |
For the purposes of our discussion it is sufficient to consider only the "classical" version of the generic shortest path problem. There are many others.
Consider then the problem consisting of n > 1 cities {1,2,...,n} and a matrix D representing the length of the direct links between the cities, so that D(i,j) denotes the length of the direct link connecting city i to city j. This means that there is at most one direct link between any pair of cities. The distances are not assumed to be symmetric, so D(i,j) is not necessarily equal to D(j,i). In this framework a path is a sequence of cities and a feasible path is a path with the property that from any city on this path there is a direct link to the next city on the path. The objective is to find the shortest feasible path from a given city h, called home, to a given city d, called destination. The length of a path is assumed to be equal to the sum of the lengths of the links between consecutive cities on the path. With no loss of generality we assume that h=1 and d=n. So the basic question is: what is the shortest path from city 1 to city n?
To be able to cope easily with situations where the problem is not feasible (there is no path from city 1 to city n) we deploy the convention that if there is no direct link from city i to city j then D(i,j) is equal to infinity. Accordingly, should we conclude that the length of the shortest path from node i to node j is equal to infinity, the implication would be that there is no (feasible) path from node i to node j.
Observe that subject to these conventions, an instance of the shortest path problem is uniquely specified by its distance matrix D. Thus, this matrix can be regarded as a complete model of the problem.
As far as optimal solutions (paths) are concerned, we have to distinguish between three basic situations:
- An optimal solution exists.
- No optimal solution exits because there are no feasible solutions.
- No optimal solution exists because the length of feasible paths from city 1 to city n is unbounded from below.
Ideally then, algorithms designed for the solution of shortest path problems should be capable of handling these three cases.
Figure 1 depicts three instances illustrating these cases. The cities are represented by the nodes and the distances are displayed on the directed arcs of the graphs. In all three cases n=4. The respective distance matrices are also provided. The symbol "*" represents infinity so the implication of D(i,j)="*" is that there is no direct link connecting city i to city j.
|
Figure 1
By inspection we see that the problem depicted in Figure 1(a) has a unique optimal path, that is x=(1,2,3,4), whose length is equal to 6. The problem depicted in Figure 1(b) does not have a feasible - hence optimal - solution. Figure 1(c) depicts a problem where there is no optimal solution because the length of a path from node 1 to node 4 can be made arbitrarily small by cycling through nodes 1,2 and 3. Every additional cycle will decrease the length of the path by 1.
Observe that if we require the feasible paths to be simple, namely not to include cycles, then the problem depicted in Figure 1(c) would be bounded. Indeed, it would have a unique optimal path x=(1,2,3,4) whose length is equal to 6. In our discussion we do not impose this condition on the problem formulation, namely we admit cyclic paths as feasible solutions provided that they satisfy the precedence constraints. Thus, x'=(1,2,3,1,2,3,4) and x"=(1,2,3,1,2,3,1,2,3,4) are feasible solutions for the problem depicted in Figure 1(c). This is why in the context of our discussion this problem does not have an optimal solution.
Let C={1,2,...,n} denote the set of cities and for each city j in C let P(j) denote the set of its immediate predecessors, and let S(j) denote the set of its immediate successors, namely set
| P(j) = {k in C: D(k,j) < infinity} , j in C | (1) | |
| S(j) = {k in C: D(j,k) < infinity} , j in C | (2) |
Thus, for the problem depicted in Figure 1(a), P(1)={}, P(2)={1}, P(3)={1,2}, P(4)={3}, S(1)={2,3}, S(2)={3}, S(3)={4}, S(4)={}, where {} denotes the empty set.
Also, let NP denote the set of cities that have no immediate predecessors, and let NS denote the set of cities that have no immediate successors, that is let
| NP = {j in C: P(j) = {}} | (3) | |
| NS = {j in C: S(j) = {}} | (4) |
Thus, in the case of Figure 1(a), NP={1} and NS={4}. Obviously, if city 1 is in NS and/or city n is in NP then the problem is not feasible.
For technical reasons it is convenient to assume that P(1) = {}, namely that city 1 does not have any immediate predecessors. This is a mere formality because if this condition is not satisfied, we can simply introduce a dummy city and connect it to city 1 with a link of length 0. We can then assume that this dummy city - rather than city 1 - is the home city. This minor modelling issue is illustrated in Figure 2.
|
Figure 2
The two problems are equivalent in the sense that the problem of finding an optimal path from city 1 to city 4 in Figure 2(a) is equivalent to the problem of finding an optimal path from city 1 to city 5 in Figure 2(b). There is a one to one correspondence between the feasible - therefore optimal - solutions to these two problems.
So with no loss of generality we assume that P(1)={}.
As far as solution methods are concerned, it is useful to classify shortest path problems as follows:
- Acyclic problems:
The network representing the problem does not contain cycles. - Cyclic problems
- Non-negative inter-city distances.
- Negative inter-city distances, but no negative path lengths.
- Negative path lengths
All the solution methods we employ in the modules are dynamic programming (DP) based. This includes the famous Dijkstra's Algorithm that is designed for problems where the inter-city distances are non-negative: cycles are welcome.
- A simple animation module for the problem itself. Strictly for fun!
- A module based on the standard dynamic programming method for Acyclic Problems.
- A simple solve-button implementation of Dijkstra's Algorithm.
- A very long interactive paper giving a DP perspective on Dijkstra's Algorithm.
- A simple implementation of the general purpose DP successive approximation method. Negative cycles are welcome.
References
Microsoft Shortest Path Algorithms Project: research.microsoft.com/research/sv/SPA/ex.html.
Moore, E.F. (1959), The shortest path through a maze, pp. 285-292 in Proceedings of an International Synposium on the Theory of Switching (Cambridge, Massachusetts, 2-5 April, 1957), Harvard University Press, Cambridge.
