迪杰斯特拉算法用于计算：某点v0到其他所有点的最短路径，时间复杂度为O(n^2)
初态：
设定V为所有顶点的集合。
设定S为已经得到的最短路径的顶点vi的集合。即S中的顶点vi，都是已经确定下来v0到vi间的最短距离的顶点的集合。
设定V-S为尚未计算得到最短路径的顶点集合。
初态下，S为空，V-S=V。
D[vi]为v0到vi的最短距离。
基本思路：
在V-S中，找一个顶点vi,该vi要满足：v0->vi间的距离，是V-S中v0到其他顶点vj的距离中最小的顶点。
现在考虑v0->vi的最短路径，这个最短路径有三种可能：
1).v0直接到vi
2).v0到S中的某个或某多个顶点vk,在经由vk回到vi
3).v0经过V-S中的某个或多个顶点vj,在经由vj回到vi.
首先考虑3),这是不可能的。因为前提是v0->vi是V-S中最短的距离，如果说v0->vj->vi的距离是最短的，则v0->vj的距离一定小于v0->vi（因为v0->vi=v0->vj+vj->vi）,而前提是假设v0->vi已经是V-S中最短的了，即v0->vj一定是大于v0->vi的，这与3)矛盾，因此只剩下1)和2)两种可能。
因此，求v0->vi的最短距离，只要考虑1)与2)即可。
基本流程：
1).在V-S中找到一个满足v0->vi最短的顶点vi.
2).更新v0经由vi到V-S中其他各点的最短距离，即如果k属于V-S且v0->vi->vk,则更新D[vk]=D[vi]+vi->vk。
循环1)与2) n-1次后，任意点vi的D[vi]即为v0->vi的最短距离长度。
不是问题的问题：
看起来在基本流程的1)与2)的过程中，没有体现出基本思路中1)vo直接到vi与2)v0到S中的某个或某多个顶点vk，在经由vk回到vi间的比较，但实际上这个比较已经发生了。
考虑正在计算v0->vi的最短路径，设定vk为计算v0->vi前的某个顶点，该顶点vk已经计算了v0->vk的最短距离并将加入到了S中。
在计算vk的过程中，在进行到基本流程的2)时:
此时开始更新v0经由vk到V-S中各点的距离，当遇到vi时，此时vi尚在V-S中，计算发现v0->vk->vi<v0->vi,则更新D[vi]=D[vk]+vk->vi。
实际上在计算v0到vi的最短路径时，基本思路中1)与2)的对比是发生在vk的，在计算vk的第二个步骤中，发现v0->vk->vi的距离小于v0->vi，并更新了D[vi]，也就是说，v0->vi和v0->经由S中的顶点->vi的距离谁更短这个问题已经在计算vi之前的顶点中发生了，当计算到vi时，此时的D[vi]已经代表了v0->vi和v0->经由S中的顶点->vi中的最小值。
原文：https://www.cnblogs.com/lxy-xf/p/11283695.html