Dag的最短路径

Question

我有一个带有s和t顶点的图形,我需要找到它们之间的最短路径.该图有许多我想要利用的特殊属性:

• 该图是DAG(有向无环图).
• 我可以在O(| V |)时间内创建拓扑排序,比传统的O(| V + E |)更快.
• 在拓扑排序中,s是列表中的第一项,t是最后一项.

我被告知,一旦我有一个拓扑排序的顶点,我可以找到比我目前Dijkstra的统一成本标准更快的最短路径,但我似乎无法找到它的算法.

伪代码将非常感激.

编辑:从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到目的地的任何最短路径.您只需要在成本映射中查找目标,获取它的父级,然后重复此过程,直到获得父级为s的节点,然后您拥有最短路径.