算法介紹

• 源點s,數組d[u]表示s到u的最短距離，空集S，點集Q
• 初始化：將源點s從點集中去掉，加入S，d[s]=0，$?v\in Q,d[v]=w[s][v]$
• 將Q中d[v]最小的點去掉加入S,并對$u\in Q,w[v][u]<\infty$進行松弛操作：如果$d[v]+w[v,u]<d[u],d[u]=d[v]+w[v,u]$
• 重復上述步驟直到Q為空集

正確性證明

Dijkstra算法條件：沒有負邊

設源點為s，d[v]表示源點到點v的舉例，d[u,v]表示點u到點v的舉例，w[u,v]表示從點u到點v的一條有向邊的長度，$\delta (s,v)$表示源點到點v的最短路徑長度。

最優子結構性質：任意兩點之間的最短路徑的子路徑仍然是最短路徑

證明：假設s到v的最短路徑上有子路徑u到w，那么$\delta (s,v)=d[s,u]+d[u,w]+d[w,v]$，$d[u,w]>\delta (u,w)$

那么將$d[u,w]$替換為$\delta (u,w)$可以得到更好的路徑，那么原路徑就不知最短路徑，這和$\delta (s,v)$的定義矛盾。因此該問題具有最優子結構性質。

引理1：初始化以后進行松弛操作前后$?v\in V,d[v]?\delta (s,v)$

證明：由初始化條件，剛初始化以后$?v\in V,d[v]?\delta (s,v)$

假設當對點v進行松弛操作時第一次導致上式不再成立，即$d[v]=d[u]+w[u,v]<\delta (s,v)$

因為點u在點v之前，所以點u滿足上述不等式，$d[u]?\delta (s,u)$

由定義容易得到$w[u,v]?\delta (u,v)$，因此$d[v]=d[u]+w[u,v]?\delta (s,u)+\delta (u,v)$

由三角不等式$d[v?\delta (s,u)+\delta (u,v)?\delta (s,v)$，與上面假設矛盾

因此初始化以后進行松弛操作前后$?v\in V,d[v]?\delta (s,v)$，引理1成立

引理2：假設存在s到v的最短路徑:s->…->u->v，$d[u]=\delta (s,u)$，那么在點u對v進行松弛操作$d[v]=d[u]+w[u,v]$之后，$d[v]=\delta (s,v)$

證明：由最優子結構性質，s到v的路徑中s到u為點u的最短路徑，$\delta (s,v)=\delta (s,u)+w[u,v]$

$d[u]+w[u,v]=\delta (s,u)+w[u,v]=\delta (s,v)$，由引理1，在松弛操作以前$d[v]?\delta (s,v)$，因此松弛操作會保證$d[v]=\delta (s,v)$，等證。

當算法結束后，$d[v]=\delta (s,v)$

證明：因為算法中將點加入確定的集合后就不再進行修改，所以相當于證明加入確定集合時$d[v]=\delta (s,v)$

由引理1，假設加入確定集合時第一個出現$d[v]>\delta (s,v)$為節點v(開始使用反證法)

假設s到v的最短路徑為s->…->x->y->…->v，x是該路徑在確定集合中的最后一個元素，y是該路徑不在確定集合中的第一個元素。

因為v是第一個出現的點，而x在v之前加入，所以$d[x]=\delta (s,x)$

由最優子結構，s->…->x->y是s到y的一條最短路徑，此時x已經進行了松弛操作

由引理2，$d[y]=\delta (s,y)$

因為y是s到v路徑上的一點，所以$\delta (s,v)?\delta (s,y)$

加入確定集合時$d[v]$是所有未加入點中最小的，所以$d[v]?d[y]=\delta (s,y)?\delta (s,v)$,與假設矛盾。證畢。

復雜度分析

初始化的復雜度為$\Theta (|V|)$

總共要循環|V|次尋找點集中d[]最小的元素，復雜度為$O(|V|T_{尋找最小元素})$

對于每個點都需要對所指向的點進行降低鍵值操作，由握手定理，總共需要降低出度的總和即|E|，復雜度為$O(|E|T_{降低鍵值})$

因此總共的復雜度為$O(|V|T_{尋找最小元素}+|E|T_{降低鍵值})$，通過使用不同的數據結構我們可以得到不同的復雜度。特殊的，如果我們使用數組，復雜度為$O(|V{|}^2)$，如果我們使用二叉堆，復雜度為$O((V+E)logV)$，如果我們使用斐波那契堆，可以得到最優秀的復雜度$O(E+VlogV)$

和BFS的關系

特殊地，如果邊的權值全部為1（或者相等），那么BFS就是Dijkstra算法，復雜度為$O(V+E)$