Last updated on: 10 November 2008 06:01:20 PM

This page will be updated with the following items:
-. This page only contain a brief information regarding Single Source Shortest Paths
The chapter in CLR is 35 pages, I will add more here later...

Go to Programming Section

Contents:

1. Introduction to Graph
2. Searching a Graph
3. Finding Connected Components (Flood Fill)
4. Minimum Spanning Trees (MST)
5. Single-Source Shortest Paths
 - Using Breadth First Search in special case
 - Relaxation
 - Dijkstra
 - Bellman-Ford
 - DAG Shortest Paths
6. All-Pairs Shortest Paths
7. Advanced Algorithms

Note: Single-source shortest paths is discussed in detail (very detail...) in Introduction to Algorithms, chapter 25.

5.1. Finding Shortest Paths using BFS

This only applicable to graph with unweighted edges, simply do BFS from start node to end node, and stop the search when it encounters the first occurrence of end node. Proof can be found in Introduction to Algorithms, chapter 23.

5.2. Relaxation

The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v. The relaxation procedure proceeds as follows:

initialize_single_source(Graph G,Node s)
  for each vertex v in Vertices(G)
    G.d[v]:=infinity
    G.pi[v]:=nil
  G.d[s]:=0;

This sets up the graph so that each node has no predecessor (pi[v] = nil) and the estimates of the cost (distance) of each node from the source (d[v]) are infinite, except for the source node itself (d[s] = 0).

Note that we have also introduced a further way to store a graph (or part of a graph - as this structure can only store a spanning tree), the predecessor sub-graph - the list of predecessors of each node, pi[j], 1 <= j <= |V|. The edges in the predecessor sub-graph are (pi[v],v).

The relaxation procedure checks whether the current best estimate of the shortest distance to v (d[v]) can be improved by going through u (i.e. by making u the predecessor of v):

relax(Node u,Node v,double w[][])
  if d[v] > d[u] + w[u,v] then
    d[v]:=d[u] + w[u,v]
    pi[v]:=u

5.3. Dijkstra Algorithm

Taken from: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html

Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is called the Single-source shortest paths problem.

This problem is related to the spanning tree. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G=(V,E) where V is a set of vertices and E is a set of edges.

Dijkstra's algorithm keeps two sets of vertices: S (the set of vertices whose shortest paths from the source have already been determined) and V-S (the remaining vertices). The other data structures needed are: d (array of best estimates of shortest path to each vertex) & pi (an array of predecessors for each vertex)

The basic mode of operation is:

1. Initialise d and pi,

2. Set S to empty,

3. While there are still vertices in V-S,

   1. Sort the vertices in V-S according to the current best estimate of their distance from source,

   2. Add u, the closest vertex in V-S, to S,

   3. Relax all the vertices still in V-S connected to u

Dijkstra Algorithm:

DIJKSTRA(Graph G,Node s)
  initialize_single_source(G,s)
  S:={ 0 }       /* Make S empty */
  Q:=Vertices(G) /* Put the vertices in a PQ */
  while not Empty(Q)
    u:=ExtractMin(Q);
    AddNode(S,u); /* Add u to S */
    for each vertex v which is Adjacent with u
      relax(u,v,w)

5.4. Bellman-Ford Algorithm

A more generalized single-source shortest paths algorithm which can find the shortest path in a graph with negative weighted edges. If there is no negative cycle in the graph, this algorithm will updates each d[v] with the shortest path from s to v, fill up the predecessor list "pi", and return TRUE. However, if there is a negative cycle in the given graph, this algorithm will return FALSE.

BELLMAN_FORD(Graph G,double w[][],Node s)
  initialize_single_source(G,s)
  for i=1 to |V[G]|-1
    for each edge (u,v) in E[G]
      relax(u,v,w)

  for each edge (u,v) in E[G]
    if d[v] > d[u] + w(u, v) then
      return FALSE
  return TRUE

5.5. Single-source shortest paths in Directed Acyclic Graph (DAG)

There exist a more efficient algorithm ~ O(V+E) ~ for solving Single-source shortest path problem for a Directed Acyclic Graph (DAG). So if you know for sure that your graph is a DAG, you may want to consider this algorithm instead of using Djikstra.

DAG_SHORTEST_PATHS(Graph G,double w[][],Node s)
  topologically sort the vertices of G // O(V+E)
  initialize_single_source(G,s)
  for each vertex u taken in topologically sorted order
    for each vertex v which is Adjacent with u
      relax(u,v,w)

A sample application of this DAG_SHORTEST_PATHS algorithm (as given in CLR book) is to solve critical path problem, i.e. finding the longest path through a DAG, for example: calculating the fastest time to complete a complex task consisting of smaller tasks when you know the time needed to complete each small task and the precedence order of tasks.

PREVIOUS - NEXT