我需要在加权无向图中找到每条边的最短替代路径，即假设我在图中有一个 egde (a,b)，那么我想计算顶点 a 和 b 之间的最短路径跳过直接路径，即 edge(a,b) 。如果没有替代路径，那么距离应该是无限的。我想对图的每条边都这样做。我尝试过使用 dijkstras 算法（遇到目标顶点时会中断），但是为每条边单独计算路径需要太多时间，特别是在没有替代方案的情况下路径是可能的（在这种情况下，必须遍历整个图）。您能否为此提出任何其他替代解决方案。
问问题
773 次
4 回答
1
我想我要做的是调整 Dijkstra 的算法，以便我最初用长度为 2 且不使用该边的所有路径填充堆/优先队列（感谢titus 发现我之前的错误）。这样，您获得的结果将排除恰好包含一条边的路径。然后，结果将为您提供一个特定来源的所有内容，您可以对所有可能的来源重复此操作。
于 2012-08-09T17:40:11.053 回答
-1
建议的解决方案Dennis Meng是我的想法。但是有一些优化（预处理）可以使您的实现更快。
将图分离为一组连通组件（树）[提示：使用 DFS 查找连通组件]。-- 这样，如果您在
tree有节点中找不到对 (u,v) 的最短路径，u那么您可以跳出（内部）循环。维护每个节点与其对应的树之间的映射。-- 这将有助于实施第 1 步
于 2012-08-09T21:43:46.457 回答
-1
这是我前段时间写的一个 dijkstra 实现，它使用stl make_heap更有效地查找下一个节点。实施很可能是正确的。
编辑：在从文件读取的示例中，n是顶点数，m是边数，a并且b是边顶点，方向是从a到b，c是权重。
正如没人提到的那样，您应该删除边缘，然后将其添加回来，以保持算法不变。
于 2012-08-09T17:27:25.217 回答
-1
在对它执行 dijkstras 之前，您只需要简单地从图中删除目标边......
于 2012-12-26T04:39:58.037 回答