Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Single-Source Shortest Path

In this section we consider the single-source shortest path problem: Given an edge-weighted graph tex2html_wrap_inline70093 and a vertex tex2html_wrap_inline70955, find the shortest weighted path from tex2html_wrap_inline70959 to every other vertex in tex2html_wrap_inline70095.

Why do we find the shortest path to every other vertex if we are interested only in the shortest path from, say, tex2html_wrap_inline70959 to tex2html_wrap_inline70961? It turns out that in order to find the shortest path from tex2html_wrap_inline70959 to tex2html_wrap_inline70961, it is necessary to find the shortest path from tex2html_wrap_inline70959 to every other vertex in G! If a vertex is ignored, say tex2html_wrap_inline70259, then we will not consider any of the paths from tex2html_wrap_inline70959 to tex2html_wrap_inline70961 that pass through tex2html_wrap_inline70259. But if we fail to consider all the paths from tex2html_wrap_inline70959 to tex2html_wrap_inline70961, we cannot be assured of finding the shortest one.

Furthermore, suppose the shortest path from tex2html_wrap_inline70959 to tex2html_wrap_inline70961 passes through some intermediate node tex2html_wrap_inline70259. That is, the shortest path is of the form tex2html_wrap_inline71015 It must be the case that the portion of P between tex2html_wrap_inline70959 to tex2html_wrap_inline70259 is also the shortest path from tex2html_wrap_inline70959 to tex2html_wrap_inline70259. Suppose it is not. Then there exists another shorter path from tex2html_wrap_inline70959 to tex2html_wrap_inline70259. But then, P would not be the shortest path from tex2html_wrap_inline70959 to tex2html_wrap_inline70961, because we could obtain a shorter one by replacing the portion of P between tex2html_wrap_inline70959 and tex2html_wrap_inline70259 by the shorter path.

Consider the directed graph tex2html_wrap_inline71043 shown in Figure gif. The shortest weighted path between vertices b and f is the path tex2html_wrap_inline71049 which has the weighted path length nine. On the other hand, the shortest unweighted path is from b to f is the path of length three, tex2html_wrap_inline71055.

   figure50849
Figure: Two edge-weighted directed graphs.

As long as all the edge weights are non-negative (as is the case for tex2html_wrap_inline71043), the shortest-path problem is well defined. Unfortunately, things get a little tricky in the presence of negative edge weights.

For example, consider the graph tex2html_wrap_inline71067 shown in Figure gif. Suppose we are looking for the shortest path from d to f. Exactly two edges emanate from vertex d, both with the same edge weight of five. If the graph contained only positive edge weights, there could be no shorter path than the direct path tex2html_wrap_inline71075.

However, in a graph that contains negative weights, a long path gets ``shorter'' when we add edges with negative weights to it. For example, the path tex2html_wrap_inline71077 has a total weighted path length of four, even though the first edge, (d,a), has the weight five.

But negative weights are even more insidious than this: For example, the path tex2html_wrap_inline71081, which also joins vertex d to f, has a weighted path length of two but the path tex2html_wrap_inline71087 has length zero. That is, as the number of edges in the path increases, the weighted path length decreases! The problem in this case is the existence of the cycle tex2html_wrap_inline71089 the weighted path length of which is less than zero. Such a cycle is called a negative cost cycle  .

Clearly, the shortest-path problem is not defined for graphs that contain negative cost cycles. However, negative edges are not intrinsically bad. Solutions to the problem do exist for graphs that contain both positive and negative edge weights, as long as there are no negative cost cycles. Nevertheless, the problem is greatly simplified when all edges carry non-negative weights.