提醒：这里读者一定要反复仔细体会
Lk
的含义，它不断更新的过程正是Dijkstra算法“由近及远，层层扩展”特点的体现。同时思考一下之前提过的“找到一个点后，该点
Lk
值肯定不会被更改”的原因（理解
Lk
的含义后，原因其实是显而易见的）。
Dijkstra算法的数学证明： 由算法的数学描述，可知： 只有命题：“每次从
Q
集中找到Lk最小的点
v
，Lv即为从起点到
v
的最短路径长度”正确时，算法正确。
可用广义数学归纳法证明，设起点为o：
证明：算法找到的第一个点为
v1
，
Lv1
即为从起点到
v1
的最短路径长度。
用反证法：
∵算法找到的第一个点一定是起点o最近的邻居
假设Lv1不是从起点到v1的最短路径长度
则∃点v，使得∣∣ov→∣∣<∣∣ov1→∣∣，与已知矛盾
故假设不成立，子命题得证
证明：已用算法从
Q
中依次找到了v1,v2,⋯,vk共
k
个点，且Lv1,Lv2,⋯,Lk是起点到各点的最短路径长度，则此时从
Q
中依照算法再找一个点vk+1，
Lk+1
即为起点到
vk+1
的最短路径长度。
用反证法：
假设Lk+1不是起点到vk+1最短路径的长度
所以设起点到vk+1的最短路径经过的点的集合为V，路径长度为L，则有L ∵由Lk的含义⇒V∩Q≠∅ 又∵o∈V且o∈S⇒V∩S≠∅ 则设到vk+1的最短路径中，最靠近vk+1且不属于S的点为vx，vx的后继为vy ∵有向图中边均为正权边 ∴必有Lvx 又∵vx∉S⇒Lvx>Lk+1，产生矛盾 故假设不成立，子命题得证 综上所述，该命题得证，故算法正确。 关于负权边 Dijkstra算法要求有向图中不得有负权边，如果图中有负权边，则在之前的证明过程中： ∵Lvx ∴Lvx>Lk+1不一定成立 故此时算法正确性不得证。 这里举一个简单的例子供读者自行对照理解： 时间复杂度 设有向图中，共有 V 个顶点，E条边。 传统Dijkstra算法中主要操作有： 每次从 Q 集中找到Lk最小的点，最坏情况下需： (V−1),(V−2),⋯,1 次操作。 所以整个算法过程共需： (V−1)+(V−2)+⋯+1=(v−1)v2=V22−12 次操作。计算并更新各点邻居的 Lk 值，实质上是将所有的边遍历一遍，故需 E 次操作。 则用大O表示法: O(V22−12+E)⇔O(n2) 故传统Dijkstra算法的时间复杂度为 O(n2) Dijkstra算法的优化 在上述对于传统Dijkstra算法的时间复杂度分析中，我们可知，（尤其是稀疏图中）从 Q 集中找到Lk最小的点的过程极大影响了算法的性能，这个过程在顶点无序状态下需要 O(n2) 的复杂度。 因此对于顶点的有效排序可以大大地提高算法的性能，常用的方法有：小顶堆或优先队列： 小顶堆优化中，我们初始将所有顶点设置为一个小顶堆，此时堆顶一定为起点，而在每一次迭代中，我们将堆顶元素取出（复杂度 O(1) ），而后调整小顶堆（复杂度 O(logn) ），这样调整 V 次，直到堆中所有顶点全部加入S。则整个算法的时间复杂度将从 O(n2) 优化为 O(nlogn) 。优先队列优化中，建立一个最小优先的优先级队列，队列中保存顶点和当前 Lk 值的二元组，初始将起点二元组入队，每当某个顶点的 Lk 值被更新，则将这个新的顶点二元组入队，每次迭代时，将队首元素取出并出队，直到队列为空。由于优先队列一般采用堆实现，故维护优先队列的复杂度同为 O(logn) ，则整个算法的时间复杂度同被优化为 O(nlogn) 。 注意：优先队列优化中，新的顶点二元组入队时，旧的二元组依然在优先队列中，因此每次出队的元素可能会有杂音，如何识别并去除这些杂音是这种优化方式需要考虑的。 关于无向图 事实上，Dijkstra算法同样可以处理无向图中的单源最短路问题（无向图其实可看做一种特殊的有向图），但在这种情况下，要对算法做一些修改：标记已经访问过的边，在寻找邻居时不沿已标记过的边寻找。 关于空间复杂度 Dijkstra算法的空间复杂度视具体实现方法而定，采用邻接矩阵的存图方式的空间复杂度为 O(n2) ，然而在稀疏图中，这种存储方式将有大量的空间浪费，因此推荐使用邻接表和有关标志数组存图。 算法具体代码实现多种多样，留作读者自行思考，在此不再赘述。 绝对原创，转载请注明出处。 才疏学浅，如有错误，望不吝赐教