Dag的最短路径

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

该图是DAG（有向无环图）。

我可以在O（| V |）时间内创建一个拓扑排序，比传统的O（| V + E |）更快。

在拓扑排序中，s是列表中的第一项，t是最后一项。

有人告诉我，一旦我有一个拓扑排列的顶点，我可以找到比我当前的Dijkstra的统一成本标准更快的最短路径，但我似乎无法找到它的算法。

伪代码将不胜感激。

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

---

我会违背我的直觉，并认为这不是功课。 你必须利用拓扑排序给你的信息。 每当你以拓扑顺序检查节点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的节点，然后您拥有最短路径。

链接地址: http://www.djcxy.com/p/35273.html

上一篇: Shortest Path For A Dag

下一篇: MST and one Claims?