6

我有一个带有 s 和 t 顶点的图，我需要找到它之间的最短路径。该图有很多我想利用的特殊属性：

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

有人告诉我，一旦我对顶点进行了拓扑排序，我就可以比我目前的 Dijkstra 统一成本标准更快地找到最短路径，但我似乎找不到它的算法。

伪代码将不胜感激。

编辑：从 s 到 t 的所有路径都具有相同数量的边。边有权重。我正在寻找成本最低的路径。

4

1 回答 1

22

我要违背我的直觉，假设这不是家庭作业。您必须利用拓扑排序为您提供的信息。每当您检查拓扑排序中的节点 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 的节点，那么你就有了最短路径。

于 2009-09-27T03:05:32.563 回答