Single Source Shortest Path – Directed Acyclic Graph

Introduction

Directed Acyclic Graph is a very special graph and has the following properties:

  • The edges of this graph are directed, it means all the edges have a designated direction.
  • There is no cycle in the graph, which means that a path will never contain one vertex more than once.

We referred to these kind of graphs in the topological ordering post.

Here we discuss the algorithm to find single source shortest path in such graphs. The good part is that unlike Dijkstra and Bellman Ford this can be solved in linear time O(E+V).

This algorithm for finding shortest path of directed acyclic graphs solves a variety of real world problems like the ones mentioned below:

  • Identifying the critical paths in PERT(Program Evaluation Review Technique) Charts
  • Work Flow in manufacturing / post processing plants.

Approach

Consider the graph below:

Shortest Path - Directed Acyclic Graph

The graph is already topologically sorted (to know more about topological ordering please refer to my previous post).

The shortest path algorithm reduces to a simple version here.

  • Iterate through each node of the topologically sorted graph.
  • Relax all the out going edges of the graph.

Relaxing is already defined in my previous posts on shortest path, here I repeat it once again for convenience.

  • Let say for any vertex v the distance d(v) is the shortest distance from source s to v.
  • Similarly for a vertex u the distance d(u) is the shortest distance from source s to u.
  • Let say that their exist an edge (u, v) with weight w.
  • Relaxing the edge (u, v) means
    • if d(v) > d(u) + w, then d(v) = d(u) + w
    • else d(v) remains unchanged

Pseudo Code

The above pseudo code accepts three arguments, a graph G (adjacency list representation), a weight function W (to represent edge weights), the source s.

Analysis

  • The first step is to sort the graph topologically which takes O(V+E) time (check my previous post).
  • The second step is to initialize the cost of each vertex to positive infinity which takes O(V) time (each vertex is visited once and assigned a default cost, the source is assigned a zero cost because it actually takes nothing to go from source to source).
  • The third step is to relax each edge in the graph which takes  O(E) time because relaxation is a constant time process.

Side Note: We see a nested loop in the last three lines, which may give an impression that the running time for these three lines is O(V.E). But that is not actually true. We are using a aggregation here, the outer loop runs for V times but the inner loop only runs for the size of the adjacency list of the current vertex. So the total number of times the loop runs would be :

N = adj(u1)+ adj(u2) + adj(u3) + … + adj(uk-1)+ adj(uk) where k is the number of vertices. Here N will be equivalent to the sum of the length of the adjacency lists of all the vertices.

Therefore the running time of the algorithm remains O(V+E) and the costliest task in the algorithm is topological sorting.