Shortest Path For A Dag
I'm going to go against my intuition and assume this isn't homework. You have to take advantage of the information that a topological ordering gives you. Whenever you examine the node n in a topological ordering, you have the guarantee that you've already traversed every possible path to n. Using this it's clear to see that you can generate the shortest path with one linear scan of a topological ordering (pseudocode):
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 look up any shortest path from s to a destination. You'd just need to look up the destination in the cost mapping, get it's parent, and repeat this process until you get a node whose parent is s, then you have the shortest path.
user108088
Updated on June 25, 2022Comments
-
user108088 almost 2 years
I have a graph with an s and t vertex that I need to find the shortest path between. The graph has a lot of special properties that I would like to capitalize on:
- The graph is a DAG (directed acyclic graph).
- I can create a topological sort in O(|V|) time, faster than the traditional O(|V + E|).
- Within the topological sort, s is the first item in the list and t is the last.
I was told that once I have a topological sort of the vertices I could find the shortest path faster than my current standard of Dijkstra's Uniform Cost, but I cannot seem to find the algorithm for it.
Pseudo code would be greatly appreciated.
EDITS: All paths from s to t have the same number of edges. Edges have weights. I am searching for lowest cost path.
-
Admin almost 14 yearsThanks for the answer but I can't seem to figure out what e.dest means? Can someone please clarify it?
-
user108088 almost 14 yearsEdges here are actually directed arcs. e.dest is the node being pointed to by the edge.
-
Fidor over 13 years"dest" stands for "destination".
-
Gin about 13 yearsI think there might be a little problem about you pseudo-code about relaxing the node e.dest. Should it be {if cost[e.dest].cost > cost[v].cost + e.weight;} ?