首页 文章

在N步骤内的DIrected非循环图最短路径

提问于
浏览 次
0

我有一个问题，即在正加权有向无环图中找到最短路径，但是限制了最大N步数（路径中的边） . 假设路径存在 . 该图的附加属性是如果边（i，j）在图中，那么任何边（i，k）也在i <k <j的图中 . 我只对图的开始和结束之间的最短路径感兴趣（在拓扑排序之后） .

我知道有一种有效的算法用于O（V E）中有向无环图中的最短路径，但它没有考虑步长限制 . 我想不出任何方法可以使它成为O（（V E）* N），但这将是理想的性能，因为它应该足以处理1000个节点和100个步骤的图形 .

例如，考虑以下graph .

问题是找到最多使用k = 3步（边）的最短路径 . 答案是6（路径1-> 4-> 5-> 6） .

algorithm graph shortest-path directed-acyclic-graphs

1 回答

  • 0

    它实际上是 O(N + M) ，其中 N 是顶点数， M 是边数 . 您可以在此处找到更多信息：http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

    找到路径（我正在使用geeksforgeeks的代码）：而不是 int dist[V] 使用 pair<int, int> dist[V] . 最初 dist[S] = {0, -1} . 所以在这种情况下 if (dist[i->getV()].first > dist[u].first + i->getWeight()) 你需要将父设置为 dist[i->getV()] = {dist[u].first + i->getWeight(), u} .

    然后使用此递归代码恢复路径：

    void restore(int v) { 
   if(dist[v].second == -1) return;
   else answer.push_back(v);
   if(v == START_POINT) return;
   restore(dist[v].second);
}

    用 restore(FINAL_POINT) 调用它

    回复于

相关问题