c++ - 图中边的顶点之间的最短路径不应是边本身

Question

我需要找到加权无向图中每条边的最短替代路径，即，假设我在图中有一个 egde (a,b)，然后我想计算顶点 a 和 b 之间的最短路径跳过直接路径，即 edge(a,b) 。如果没有替代路径，那么距离应该是无限的。我会为图形的每条边执行此操作。我尝试使用 dijkstras 算法(遇到目标顶点时会中断)但是为每条边单独计算路径需要太多时间，特别是在没有其他选择的情况下路径是可能的(在这种情况下，必须遍历整个图)。您能否对此提出任何其他替代解决方案。

Answer 1

我想我要做的是调整 Dijkstra 的算法，以便我最初使用所有不使用该边的长度为 2 的路径填充堆/优先级队列(感谢 titus 发现了我之前的错误)。这样，您得到的结果将排除只包含一条边的路径。然后，结果会为您提供一个特定来源的所有内容，您可以对所有可能的来源重复此操作。