The shortest way for dag

Question

I have a graph with s and t vertices that I need to find the shortest path between them. A graph has many special properties that I would like to take advantage of:

• A graph is a DAG (directed acyclic graph).
• I can create a topological view in O (| V |), faster than traditional O (| V + E |).
• In topological sorting, s is the first element in the list, and t is the last.

I was told that as soon as I have a topological view of the vertices, I could find the shortest path faster than my current Uniform Cost Dijkstra standard, but I cannot find an algorithm for it.

Pseudo code is welcome.

edits: All paths from s to t have the same number of edges. The edges have weight. I am looking for the cheapest way.

Answer 1

I am going to go against my intuition and assume that this is not homework. You must take advantage of the information that the topological order gives you. Whenever you explore node n in a topological order, you have the guarantee that you have already gone through all possible paths to n. Using this, it is clearly seen that you can generate the shortest path with a single linear scan of the topological ordering (pseudo-code):

Graph g Source s top_sorted_list = top_sort(g) cost = {} // A mapping between a node, the cost of its shortest path, and //its parent in the shortest path for each vertex v in top_sorted_list: cost[vertex].cost = inf cost[vertex].parent = None cost[s] = 0 for each vertex v in top_sorted_list: for each edge e in adjacensies of v: if cost[e.dest].cost > cost[v].cost + e.weight: cost[e.dest].cost = cost[v].cost + e.weight e.dest.parent = v 

Now you can find any shortest path from s to your destination. You just need to find the destination in the cost comparison, get its parent and repeat this process until you get the node whose parent is s, then you have the shortest path.