给定一个加权无向图，开始和结束顶点，我需要找到完全相等的(在权重总和中)最短路径的数量，这些路径不在任何边缘相交。
我在这里尝试使用 Ford-Fulkerson 算法，但它只给出了可能的最大数量，并没有找到最短路径。
在 Ford-Fulkerson 期间使用 Dijkstra 算法寻找路径也无济于事，因为它可能会找到一条或多条边连接最优解路径的路径。
据我所知，有一些类似问题的答案，但使用的是未加权和有向图。我想我需要某种蛮力方法来按某种顺序去除边缘。或者可能有解决此问题的已知方法？谢谢。
编辑 1:这是显示 Dijkstra 走错路的示例的图表。红色边缘(最有可能)将首先被发现，这将使最佳解决方案成为不可能。我看到算法的目标是以某种方式移除所有红色边缘并执行 Vedang Mehta 建议的操作
最佳答案
我们可以先计算dis[u] := 从start到u的最短路径的长度。
然后我们从dis[]和G构造一个有向图(流网络)G':
检查 G 中的每条边 (u,v)
if dis[u] = dis[v] + weight(u,v) then add a direct edge (u->v) to G'(capacities 1)
if dis[v] = dis[u] + weight(u,v) then add a direct edge (v->u) to G'(capacities 1)
非边相交的最短路径的最大数目恰好是
G' 上从起始顶点到结束顶点的最大流量。
正确性证明
显而易见。
这是一个实现
关于algorithm - 查找非边缘相交的最短路径的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37595234/