Single Source Shortest Path – Directed Acyclic Graph

An interesting application

A typical workflow process might have the following scenarios:

• It has multiple tasks to be performed.
• Most of the tasks are dependent on one another.
• Due to the dependencies, the tasks has to be performed in some sequences.
• To complete the workflow there can be one or many sequences to be completed.
• The sequences might not all complete at the same time. Some might take a larger time than the others.

Critical path is defined as the sequence of tasks which takes the longest time to complete. This is named so because until this path is executed, the job is not consider to be complete and because it takes the longest time to complete, it is the deciding factor.

Applying the Shortest Path in DAG to Identify Critical Path

Here is the above graph which represents various tasks dependencies.

The tasks are represented by the edges and the edge weight is the amount of time taken to finish the task. The vertices are the mile stones in the work flow process.

Here the vertices are topologically ordered (To know more about topological ordering please refer to my previous post).

If we manage to find the shortest path(in terms of time) in the above graph, it will give us the sequence (or the path) which will finish the earliest. However, the problem we are trying to fix is the critical path problem, which means the sequence (or path) which finishes up at the end or takes the longest time to finish.

How to find that?

• It is pretty interesting to note that the relaxation step if reversed and the cost of each vertex is initialized to a negative infinity. The algorithm will find the longest path or the critical path.
• Reversing the relaxation step means
• if d(v) < d(u) + w, then d(v) = d(u) + w
• else d(v) remains unchanged
• Another possible way of doing so is to negate the edge weights. The algorithm running for shortest path will still run and finding the smallest path. The path with the smallest negative value would actually give the longest path or the critical path.

Conclusion

Many interesting applications can be solved using the shortest path in DAGs. Its fancy to say that the shortest path algorithm is linear time. Of course the constraint is to have a DAG.

Worth noticing that, the algorithm is similar to Dijkstra and Bellman Ford in terms of feature. It provides single-source-shortest-paths. Next we will discuss about all source shortest path in the Floyd Warshall Algorithm.

I hope you enjoyed this post, in case there is still something unclear, you can inform me in the comments section.