topological ordering

Single Source Shortest Path – Directed Acyclic Graph

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 ...
Read More