algorithm - 需要帮助解决这种最短路径算法的变化

Question

下图是三星面试时被问到的问题的代表。我必须编写程序来找到 I 和 M 之间的最小距离。还有一个额外的约束，我们可以更改其中一条边。例如，可以移动边 FM 连接边 L 和 M，边值仍然为 4。

如果您注意到，通过 I-> E -> F -> G -> M，I 和 M 之间的距离是 20。但是，如果我们更改其中一条边，使得 L 到 M 边的值现在为 4。我们现在必须移动边缘 FM 以加入 L 和 M。通过这种方法，I和M之间的距离为20。

任意一条边u,v可以变为u,t或t,v。它不能更改为 x,y。因此边中的一个顶点必须相同。

请找到下面的图片来说明场景 -

所以我的问题是我必须为此编写程序。为了找到两个顶点之间的最小距离，我想到了使用 Djikstra 算法。但是，我不确定如何处理我可以选择更改其中一个顶点的附加约束。如果我能得到一些帮助来解决这个问题，我将不胜感激。

Answer 1

1. 如果我们移动一条边 (A, B) , 新的结束应该是开始 S或目标 T顶点(否则，答案不是最优的)。

2. 假设我们移动边 (A, B)新的结尾是T (它是 S 的情况类似处理)。我们需要知道从 S 开始的最短路径至 A不使用此边缘(一旦我们知道，我们可以使用 S->A->T 路径更新答案)。

3. 让我们从 S 计算最短路径使用 Dijkstra 算法到所有其他顶点。

4. 让我们修复一个顶点A并计算 dist[B] + weight(A, B) 的两个最小值对于所有 B毗邻 A .让我们遍历与 A 相邻的所有边.设当前边为(A, B) .如果dist[B] + weight(A, B)等于第一个最小值，设d成为第二个最小值。否则，让 d成为第一个最小值。我们需要用 d + weight(A, B) 更新答案(这意味着 (A, B) 现在变成了 (A, T))。

此解决方案与图的大小成线性关系(不计算 Dijkstra 算法的运行时间)。

为了避免代码重复，我们可以处理边被重定向到S的情况。通过交换 S和 T并运行相同的算法(最终答案是这两次运行结果中的最小值)。