需要协助解决这个最短路径算法的变种。

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算法。然而，我不确定如何处理额外的约束条件，即我可以更改其中一个顶点的选项。如果我能得到一些帮助来解决这个问题，我会非常感激。

- user3276247

---

移动边缘是什么意思？ - kraskevich

这是否意味着我们可以取任意一条边(u, v)并将其更改为(u, t)或(t, v)，其中t是任意顶点？ - kraskevich

@kraskevich，您的理解是正确的。任意边缘u，v可以更改为u，t或t，v。但不能更改为x，y。 - user3276247

Answer 1

在你展示的图中，我看到的最短路径是 I -> E -> F -> M，长度为13。

将边 F -> M 移动，以便它连接到 L -> M 只会让事情变得更糟。新的最短路径是 I -> E-> F -> L -> M，长度为18。

显而易见的答案是将边缘 F -> M 移动，使其直接连接 I 和 M，从而得到长度为4。

换句话说，找到与I或M相连的最短边，并使用它将I直接连接到M。

未来参考，面试中极少会要求您从记忆中实现Djikstra算法。因此，您需要寻找更简单的东西。

- user3386109

---

感谢您的努力。实际上，如果F->M的值为9，则长度为13的路径将无效。另外，关于您在最后一张图中尝试的I->M连接是无效的，因为您只能更改边缘的一个顶点而不是两个顶点。这是约束条件-任意边u、v可以更改为u、t或t、v。它不能更改为x、y。因此，边缘中的一个顶点必须相同。 - user3276247

@user3276247，我将边缘F，M更改为I，M。因此，其中一个顶点（M）是相同的。 - user3386109

Answer 2

1. 如果我们移动一条边 (A, B)，新的终点应该是起点 S 或者目标点 T（否则，答案不是最优的）。

2. 假设我们移动了边 (A, B)，新的终点是 T（当它是 S 时，处理方式类似）。我们需要找出从 S 到 A 的最短路径，不使用这条边（一旦找到它，我们就可以通过 S->A->T 路径更新答案）。

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

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

这个解决方案在图的大小上是线性的（不计算Dijkstra算法的运行时间）。

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

- kraskevich