查找非边缘相交的最短路径的数量
Find number of non edge-intersecting shortest paths
给定一个加权无向图，开始和结束顶点，我需要找到 不相交于任何边 的最短路径的数量（在权重总和中）。
我在这里尝试使用 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'上从起始顶点到结束顶点的最大流量。
正确性证明
显而易见。
这是一个实现
给定一个加权无向图，开始和结束顶点，我需要找到 不相交于任何边 的最短路径的数量（在权重总和中）。
我在这里尝试使用 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'上从起始顶点到结束顶点的最大流量。
正确性证明
显而易见。
这是一个实现