Dijkstra算法概念

Question

我只是在学习Dijkstra算法，只是有点困惑

If min(A,B) = x;
   min(A,C) = y;
   min(B,C) = must be x-y;

请为它辩护，还是我错了？

Answer 1

好吧，这就是你想说的话：

我将在所有这些中提到一个有向的非负权重图。

最短路径问题：

对于有向图G和V中的节点r和实代价向量(c_e:e，E) (我希望这里有LaTeX )

我们希望发现：

对于V中的每一个v，一个从r到v的最小成本的双路径(假设它存在)

，这是你想要的东西的要点：

假设我们知道，对于V中的每个V，都有一个从r到v的路径，并且我们在E中找到了满足y_v + c_vw < y_w的边vw。

因为将vw附加到dipath到v(获取w的路径)将给出长度为y_v+c_vw的路径

最小代价双路径满足：

y_v+c_vw >= y_w为E中的所有大众服务

我们称这样的y向量为“可行势”。

命题: y_v是最小

设y是一个可行势，P是从r到v的一条双路径，则它遵循c(P) >= y_v

证明：

c(P) =和c_ei (路径的第一个边)

回想一下，一个可行的潜力统计y_v + c_vw >= y_w

所以c_vw >= y_w - y_v ，这就是

因此

c(P) >=和(y_vi-y_v{i-1}) (第一项的费用取前一项的费用)

如果将其写为sum (-y_v{i-1} + y_vi)，则展开sum：(显然y_v0=0)

-y_v0+y_v1 -y_v1 + y_v2 -.-y_v{k-2} + y_v{k-1} -y_v{k-1} + y_vk

你看到所有的条款都被取消了，给出：

c(P) >= y_vk - y_v0 = y_vk

因此，我们展示了c(P) >= y_vk

Answer 2

这是错误的，考虑任何等边三角形，两边的差值是0，而第三个大小的长度不是。