We are going to make a big assumption: that all the edges have lengths that are positive numbers. This is often but not always the case; it makes sense in the examples above, but it is conceivable that an airline could pay people to take certain routes, so that the lengths of those edges in the airport graph might be negative. We'll pretend this never happens. It makes the algorithms a lot easier. Later we'll see some special cases where we can handle negative weights.
Therefore if we only know the correct value of x we can find a shortest path:
Algorithm 1:
for each vertex y in sorted order by d(s,y)
let (x,y) be an edge with d(s,x)+length(x,y)=d(s,y)
path(s,y) = path(s,x) + edge (x,y)
We will want to use something like this idea to compute shortest
paths without already knowing their lengths. When we get to y in
the loop, it will still be ok to use terms like d(s,x) if this is
less than d(s,y), because we will have already processed x in a
previous iteration. But the pseudo-code above uses d(s,y) itself
twice, and this will not work as well.
To get rid of the second use of d(s,y), in which we test to determine which edge to use, we can notice that (because we are computing a shortest path) d(s,x)+length(x,y) will be less than any similar expression, so instead of testing it for equality with d(s,y) we can just find a minimum:
Algorithm 2:
for each vertex y in sorted order by d(s,y)
let (x,y) be an edge with x already processed,
minimizing d(s,x)+length(x,y)
path(s,y) = path(s,x) + edge (x,y)
d(s,y) = d(s,x) + length(x,y)
Algorithm 3: (Dijkstra, basic outline)
let T be a single vertex s
while (T has fewer than n vertices)
{
find edge (x,y)
with x in T and y not in T
minimizing d(s,x)+length(x,y)
add (x,y) to T
d(s,y)=d(s,x)+length(x,y)
}
The actual shortest paths can be found by following the path in T from s to t. This defines a structure known as a "shortest path tree". In practice it may sometimes faster to build two trees, one from s and one from t, and stop when they run into each other (this usually ends up visiting less of the graph).
Just like with Prim's algorithm, we can use heaps to perform the hard part of each iteration (finding the best edge) in logarithmic time.
Algorithm 4: (Dijkstra with heaps)
make a heap of values (vertex,edge,distance)
initially (v,-,infinity) for each vertex
let tree T be empty
while (T has fewer than n vertices)
{
let (v,e,d(v)) have the smallest weight in the heap
remove (v,e,d(v)) from the heap
add v and e to T
set distance(s,v) to d(v)
for each edge f=(v,u)
if u is not already in T
find value (u,g,d(u)) in heap
if d(v)+length(f) < d(g)
replace (u,g,d(g)) with (u,f,d(v)+length(f))
}
Just as in Prim's algorithm, this runs in time O(m log n) if you
use binary heaps, or O(m + n log n) if you use Fibonacci heaps.
2
A-----B
\ /
3 \ / -2
C
If we start with A, Dijkstra's algorithm will choose the edge (A,x)
minimizing d(A,A)+length(edge), namely (A,B). It then sets d(A,B)=2
and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only
choice is (A,C) and it sets d(A,C)=3. But it never finds the
shortest path from A to B, via C, with total length 1.
Algorithm 5: (shortest paths from topological order)
for each vertex y in a topological ordering of G
choose edge (x,y) minimizing d(s,x)+length(x,y)
path(s,y) = path(s,x) + edge (x,y)
d(s,y) = d(s,x) + length(x,y)
This runs in linear time (with the possible
exception of finding the ordering), and works even when the graph
has negative length edges. You can even use it to find longest
paths: just negate the lengths of all the edges. The only catch is
that it only works when we can find a topological ordering.
Theorem: a graph has a topological ordering if and only if it is a directed acyclic graph.
One direction of the proof is simple: suppose G is not a DAG, so it has a cycle. In any ordering of G, one vertex of the cycle has to come first, but then one of the two cycle edges at that vertex would point the wrong way for the ordering to be topological. In the other direction, we have to prove that every graph without a topological ordering contains a cycle. We'll prove this by finding an algorithm for constructing topological orderings; if the algorithm ever gets stuck we'll be able to use that information to find a cycle.
Algorithm 6: (topological ordering)
list L = empty
while (G is not empty)
find a vertex v with no incoming edges
delete v from G
add v to L
If this algorithm terminates, L is a topological ordering, since we
only add a vertex v when all its incoming edges have been deleted,
at which point we know its predecessors are already all in the
list.
What if it doesn't terminate? The only thing that could go wrong is that we could be unable to find a vertex with no incoming edges. In this case all vertices have some incoming edge. We want to prove that in this case, G has a cycle. Start with any vertex s, follow its incoming edge backwards to another vertex t, follow its incoming edge backwards again, and so on, building a chain of vertices ...w->v->u->t->s.
We can keep stepping backwards like this forever, but there's only a finite number of vertices in the graph. Therefore, we'll eventually run into a vertex we've seen before: u->w->v->u->t->s. In this case, u->w->v->u is a directed cycle. This procedure always finds a directed cycle whenever algorithm 6 gets stuck, completing the proof of the theorem that a graph has a topological ordering if and only if it is a DAG. Incidentally this also proves that algorithm 6 finds a topological ordering whenever one exists, and that we can use algorithm 6 to test whether a graph is a DAG. Putting algorithm 6 together with the "stepping backwards" procedure provides a fast method of finding cycles in graphs that are not DAGs.
Finally, let's analyze the topological ordering algorithm. The key step (finding a vertex without incoming edges) seems to require scanning the whole graph, but we can speed it up with some really simple data structures: a count I[v] of the number of edges incoming to v, and a list K of vertices without incoming edges.
Algorithm 7: (topological ordering, detailed implementation)
list K = empty
list L = empty
for each vertex v in G
let I[v] = number of incoming edges to v
if (I[v] = 0) add v to K
while (G is not empty)
remove a vertex v from K
for each outgoing edge (v,w)
decrement I[w]
if (I[w] = 0) add w to K
add v to L
It is not hard to see that this algorithm runs in linear time, so
combining it with algorithm 5 we see that we can find shortest
paths in DAGs in linear time.
ICS 161 -- Dept.
Information & Computer Science -- UC Irvine
Last update: