In Prim’s algorithm for minimum spanning trees:
MST-PRIM(G,w,r)
1. for each u in V2. key[u] = INFINITY
3. p[u] = NULL
4. key[r] = 05. Q = CREATE-MIN-QUEUE(V)6. while Q != {}7. u = EXTRACT-MIN(Q)
8. for each v adjacent to u
9. if v is in Q and w(u,v) < key[v]
10. p[v] = u
11. key[v] = w(u,v)
12. A = {(v,p[v]): v is in V – {r}}
13. return A
We have used a technique called relaxation. On each vertex in the priority queue, we maintain a property key[v], which is an upper bound of our
Estimate of the vertex’s distance from the spanning tree that we are growing. Initially, key[v] for all vertices is set to INFINITY. When we add
a vertex to the tree, we relax all of it’s neigbhors (lines 9-11).
Another algorithm that uses relaxation is for solving the problem of sinle source shortest paths:
For a given weighted, directed graph G=(V,E) and a source vertex s, find a shortest path from s to all the vertices in V.
A shortest distance b(s,v) is defined as INFINITY, if there is no path from s to v, and as MIN(w(p): p is a path from s to v) where w(p) for a path p
is a sum of weights of all edges on path p.
Negative-weight edges can be a problem in finding the solution to the SSSP problem. Most of the algorithms can deal with them, as
long as there are no negative-weight cycles in the graph. Some algorithms require strictly positive weights, while some allow negative weights
and report if there are negative-weight cycles.
SSSP can be represented with a shortest-path tree. Very similar to BFT. Actually, BFT is a simple instance of the SSSP problem when the
weights for all the edges are 1. We will represent the shortest-path tree with a predecessor tree, the same as in BFT. We will also maintain a property
d[v] for every vertex v in the graph that will be our upper bound estimate of the shortest path from s to v. Iterating over edges in the graph and
relaxing this property for every edge eventually leads to the SSSP solution.
Initialization:
INITIALIZE-SINGLE-SOURCE(G,s)
1. for each vertex v in V2. d[v] = INFINITY
3. p[v] = null
4. d[s] = 0Relaxation:
RELAX(u,v,w)
1. if d[v] > d[u] + w(u,v)2. d[v] = d[u] + w(u,v)
3. p[v] = u
There are some important properties of the shortest paths and the relaxation as we defined it above:
Triangle inequality: For any edge (u,v) in E, b(s,v) <= b(s,u) + w(u,v)
Upper-bound property: We always have d[v] >= b(s,v) for all vertices v in V, and once d[v] achieves the value b(s,v) it never changes.
No-path property: If there is no path from s to v, than we always have d[v] = b(s,v) = INFINITY
Convergence property: If s to u followed by (u,v) edge is a shortest path from s to u and v, and if d[u] = b(s,u) at any time prior to relaxing edge (u,v), then d[v] = b(s,v) after relaxation.
Path-relaxation property: If p = <v0, v1, …, vk> is a shortest path from s = v0 to vk, and the edges of p are relaxed in order (v0,v1), (v1,v2), … (vk-1, vk), then d[vk] = b(s, vk),
regardless of any other relaxation steps, even if they are intermixed with relaxations of edges in p.
Predecessor-subgraph property: Once d[v] = b(s,v) for all v in V, the predecessor subraph is a shortest-paths tree rooted at s.
A very simple algorithm. Runs in O(VE) time. Returns TRUE if there are negative-weight cycles in the graph, FALSE otherwise..
BELLMAN-FORD(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)2. for i = 1; i <|V|; i++3. for each edge (u,v) in E
4. RELAX(u,v,w)
5. for each edge (u,v) in E6. if d[v] > d[u] + w(u,v)
7. return FALSE
8. return TRUEAn example of Bellman-Ford algorithm execution. The edges in the example are always relaxed in following order: (t,x), (t,y), (t,z), (x,t), (y,x), (y,z), (z,x), (z,s), (s,t), (s,y).
We can notice that if we are clever about choosing the order in which the edges are relaxed, we can significantly reduce the execution time. What if we have a DAG instead
of a general graph to find the SSSP? If we topologically sort the graph and relax the edges in topological order of their source, we can reduce the running time to O(E+V). DAG’s
have a nice property that there are no cycles, so we don’t have to worry about negative cycles.
DAG-SHORTEST-PATHS(G,w,s)
1. topologicaly sort the vertices of G2. INITIALIZE-SINGLE-SOURCE(G,s)3. for each vertex u, taken in topologigal order4. for each vertex v adjacent to u
5. RELAX(u,v,w)
For directed, weighted graphs with non-negative weights, we can improve on the running time of Bellman-Ford
algorithm by using priority queue, very similar to Prim’s minimum spanning tree algorithm.
Since there are no negative-weight edges, there won’t be any negative weight cycles, so we don’t have to worry about them.
The idea is the same as in Prim’s algorithm: Keep a set S that is the current solution (a set of vertices for which the shortest paths have
already been computed), and keep all the rest in a min-priority queue. Remove a vertex v with the smallest estimate from the queue, add
it to S and relax all the v’s neigbhors.
DIJKSTRA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)2. S = {}3. CREATE-MIN-QUEUE(V)4. while Q != {}5. u = EXTRACT-MIN(Q)
6. S = S + {u}
7. for each vertex v adjacent to u
8. RELAX(u,v,w)
An example of Dijkstra’s algoritm.
The running time of Dijsktra’s algorithm depends on our min-priority queue implementation. If the vertices are numbered 1 to |V|, we can store d[v] in
corresponding entry in the array. Each INSERT (implicit in line 3) and DECREASE-KEY(implicit in line 8) operation takes O(1) time, while EXTRACT-MIN takes O(V) time.
Line 3 takes O(V) time, line 5 executes O(V) times, while line 8 executes O(E) times, so the total time is O(V + V2 + E) = O(V2).
If the graph is sparse, we can use binary min-heap to implement the min-priority queue. EXTRACT-MIN now takes O(log V) time, line 3 takes O(V) time, and
DECREASE-KEY takes O(log V) time. Total time is O(V + V log V + E log V) = O(E log V).
If we use Fibonacci heap, we can achieve a running time of O(E + V log V), same as Prim’s algorithm.