algorithm - 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 的节点，然后您就有了最短路径。