我正在学习Dijkstra算法，对此有些困惑
If min(A,B) = x;
min(A,C) = y;
min(B,C) = must be x-y;
请说明这一点，否则我错了？
好的，这就是您要说的：
在所有这些中，我将引用有向非负权重图。
最短路径问题：
对于图G和V中的节点r和实际成本向量（E中的c_e：e）（我希望我们在这里有LaTeX）
我们希望找到：
对于V中的每个v，从r到v的最小成本（假设存在）
这是您想要的要点：
假设我们知道V中每个v都有从r到v的成本y_v的路径，并且我们找到E中满足y_v + c_vw <y_w的边vw
由于将vw附加到v的dipath（以获取w的路径），因此给出的路径长度为y_v + c_vw
最小成本偏差满足：
y_v + c_vw> = y_w对于E中的所有vw
我们称这样的矢量为“可行潜力”
命题：y_v是最小的
设y为可行势，设P为从r到v的双径，则其遵循c（P）> = y_v
证明：
c（P）=总和c_ei（路径成本中的第i个边）
回想一下可行的潜在统计量y_v + c_vw> = y_w
所以c_vw> = y_w-y_v这就是你所拥有的
因此
c（P）> = sum（y_vi-y_v {i-1}）（第i个项目的成本取上一个项目的成本）
如果将其写为总和（-y_v {i-1} + y_vi），则扩展总和：（显然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
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句