最快的路径 [英] Shortest Path For A Dag

问题描述

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

I have a graph with an s and t vertex that I need to find the shortest path between. The graph has a lot of special properties that I would like to capitalize on:

• 该图是DAG（有向无环图）。 / li>
  
• 我可以在O（| V |）时间内创建拓扑排序，比传统的O（| V + E |）更快。


• 在

有人告诉我，一旦我有了一个拓扑结构，则s是列表中的第一项。在某种顶点上，我可以找到比我当前的Dijkstra统一成本标准更快的最短路径，但是我似乎找不到它的算法。

I was told that once I have a topological sort of the vertices I could find the shortest path faster than my current standard of Dijkstra's Uniform Cost, but I cannot seem to find the algorithm for it.

伪代码是

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

EDITS: All paths from s to t have the same number of edges. Edges have weights. I am searching for lowest cost path.

推荐答案

我要违背我的直觉，并假设这不是不是功课。您必须利用拓扑顺序提供的信息。每当您以拓扑顺序检查节点n时，都可以确保已遍历到n的所有可能路径。使用此方法，您可以清楚地看到，您可以通过一次线性扫描拓扑顺序（伪代码）来生成最短路径：

I'm going to go against my intuition and assume this isn't homework. You have to take advantage of the information that a topological ordering gives you. Whenever you examine the node n in a topological ordering, you have the guarantee that you've already traversed every possible path to n. Using this it's clear to see that you can generate the shortest path with one linear scan of a topological ordering (pseudocode):

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的节点，然后路径最短即可。

Now you can look up any shortest path from s to a destination. You'd just need to look up the destination in the cost mapping, get it's parent, and repeat this process until you get a node whose parent is s, then you have the shortest path.

这篇关于最快的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！