我有与S和T顶点，我需要找到之间的最短路径图。 该图有很多，我想利用特殊属性：
- 该图是一个DAG（有向无环图）。
- 我可以创建在O拓扑排序（| V |）的时间，比传统快Ò（| V + E |）。
- 在拓扑排序，s是在列表中的第一项，t是最后一次。
有人告诉我，一旦我有一个拓扑排序的顶点，我能找到的最短路径比我目前的Dijkstra的统一成本标准快，但我似乎无法找到它的算法。
伪代码将不胜感激。
EDITS：所有从s至t的路径具有相同数量的边缘。 边缘具有权重。 我在寻找最低成本路径。
Answer 1:
我要去对我的直觉和假设，这不是功课。 你必须采取的一个拓扑顺序给你的信息优势。 当您检查节点n拓扑排序，你有你已经走过每一个可能的路径为n的保证。 使用这种很明显地看到，您可以用拓扑排序（伪）的一个线性扫描生成的最短路径：
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
现在你可以看一下从s任何最短路径到目的地。 你只需要查找目的地在成本映射，得到它的母公司，直到你得到其母公司是个节点，那么你必须在最短的路径重复此过程。
文章来源: Shortest Path For A Dag
