單源最短路徑：Dijkstra演算法（堆優化）
前言：趁著對Dijkstra還有點印象，趕快寫一篇筆記。
注意：本文章面向已有Dijkstra演算法基礎的童鞋。
簡介
單源最短路徑，在我的理解里就是求從一個源點（起點）到其它點的最短路徑的長度。
當然，也可以輸出這條路徑，都不是難事。
但是，Dijkstra不能處理有負權邊的圖。
解析
註：接下來，我們的源點均默認為1。
先上程式碼（注意，是堆優化過的！！）：
struct node{
int id;
int total;
node(){};
node(int Id,int Total){
id=Id;
total=Total;
}
bool operator < (const node& x) const{
return total>x.total;
}
};
void dijkstra(int start){
memset(dis,inf,sizeof(dis));
memset(conf,false,sizeof(conf));
memset(pre,0,sizeof(pre));
dis[start]=0;
priority_queue <node> Q;
Q.push(node(1,0));
while(Q.size()){
int u=Q.top().id;
Q.pop();
if(conf[u])
continue;
conf[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
int cost=dis[u]+e[i].w;
if(cost < dis[v]){
dis[v]=cost;
pre[v]=u;
Q.push(node(v,dis[v]));
}
}
}
}
接下來，一步一步解析程式碼：
首先是結構體node
struct node{
int id;
int total;
node(){};
node(int Id,int Total){
id=Id;
total=Total;
}
bool operator < (const node& x) const{
return total>x.total;
}
};
這裡的id就是這個結點的編號，total就是走到當前節點的最小花費。
構造函數就不用我多說了吧。
因為在原始的Dijkstra中，每次都要選出當前花費最小的那個點，如果採用堆優化，使得堆頭永遠都是花費最小的那個，這樣每次選出花費最小的那個點的時間複雜度從\(O(n)\)驟降到\(O(logn)\)。
如果要用到堆，就可以使用STL的優先隊列（priority_queue）。
因為優先隊列默認是優先順序最高的放在最前面，在Dijkstra中，優先順序就是這個node的total，total越小優先順序就越高。
因為total越大，優先順序越低，所以這裡的小於運算符就可以定義為total>x.total。
接下來是初始化
memset(dis,inf,sizeof(dis));
memset(conf,false,sizeof(conf));
memset(pre,0,sizeof(pre));
dis[start]=0;
Q.push(node(1,0));
數組dis[i]表示的是從源點到點i的最短路的長度，初始時不知道能不能到達，設為inf（無窮大）。
數組conf[i]表示的是點i的最短路徑是否確認，若是，則為true，否則為false。
數組pre[i]表示的是點i的前驅，即到點i的前一個點的編號。
例如有一條最短路徑是這樣的：1->3->8->5->2，那麼pre[2]=5;pre[5]=8;pre[8]=3;。
這樣一來，輸出路徑就好辦了：
//假設要輸出到2的路徑
int i=2;
while(pre[i]!=1){
ans.push(i);
i=pre[i];
}
printf("1");
while(!ans.empty()){
printf("->%d",ans.top());
ans.pop();
}
此外，一開始從結點1出發，到結點1的距離為0，知道這些資訊後，將源點入堆。
Q.push(node(1/*節點編號*/,0/*到該節點距離*/));
接下來是重點了，我們再次一步步地拆分：
int u=Q.top().id;
Q.pop();
if(conf[u])
continue;
conf[u]=true;
這個應該不難理解，首先拿出一個源點u，u的編號自然是Q.top().id。接下來Q.pop()必不可少。
這時候，如果conf[u]==true，即結點u的最短路長度已經確定過了，那就沒必要再走了，因為之前肯定走過了。直接continue看下一個結點。
如果沒有，按照Dijkstra的特性，當前結點u的總路徑長度肯定是最短了，那麼就被確定了，conf[u]=true。
然後是下一段：
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
int cost=dis[u]+e[i].w;
if(cost < dis[v]){
dis[v]=cost;
pre[v]=u;
Q.push(node(v,dis[v]));
}
}
這段其實好理解，不過我用的是鏈式前向星存圖，如果你用的是vector做的鄰接表，其實大體上是相同的。
如果你用的是鄰接表或鄰接矩陣，這裡的v其實就是當前找的這條路的終點（e[i].v表示的是這條邊的終點。
而cost，則是dis[u]的值加上這條邊的權值（沒錯，e[i].w表示的是這條邊的權值），也就是到點v的總花費。
如果cost<dis[v]，即當前這條路到v的總花費比原來到v的總花費小，就可以更新了：
dis[v]=cost;
pre[v]=u;
Q.push(node(v,dis[v]));
首先是總花費更新，然後再更新前驅，最後把這個到過的點放入優先隊列里。
至此，堆優化Dijkstra就結束了。
但是有一個比較關心的點：時間複雜度是多少呢？
首先考慮有哪些結點會被搜索：
顯然是一開始conf[u]==false的結點，而一點出堆之後，conf[u]=true，所以有n個節點會被搜索同時入隊，每次入隊需要\(O(logn)\)。
接下來是遍歷每個結點的邊，如果用\(E_i\)表示和結點\(i\)相鄰的邊的數量，顯然有：\(\sum_{i=1}^n E_i = m\)，在最壞情況下，每次搜索邊的時候都要入隊一次，那麼總時間複雜度就是：\(O(mlogn)\)。
完結撒花✿
未經部落客允許禁止轉載！
