原理解釋

首先解釋一下它大概的應用場景以及原理：現在有這么一張圖，圖上各點之間都有一定的邊權或者說是距離。給定你一個起點（例如點1），讓你求這個點到圖上所有點的最短距離是多少？

這個問題比較平常，但是突然這么一問如果之前沒有學過此算法肯定一臉懵。接下來簡單解釋一下算法的實現思路。

實現思路

• 定義一個距離數組d[]表示起點到此點的最短距離，除了此時的點全部賦為inf

• 定義一個標記數組v[]用來判斷此點是否訪問過，避免重復訪問

• 對于這個點，每次對它的出點進行遍歷，找到距離最小的點處理

• 如果說此時這條路徑到達一個點比之前的路徑到達它的距離短，就進行更新

  • 例如點1到點3：
  • 原本是1->3，距離為5
  • 后來路徑為1->4->3，距離為4
  • 此時就可以對d[3]進行更新

• 最后輸出d數組就是起點到所有點的距離了

實現過程演示

代碼

vector<pii> e[N];
int d[N],vis[N];
void dji(int s)
{for(int i=0; i<=n; i++) d[i]=INF;d[s]=0;for(int i=1; i<n; i++)//遍歷枚舉所有點{int u=0;for(int j=1; j<=n;j++)//每次找到此點出點的距離最近點if(!vis[j]&&d[j]<d[u]) u=j;vis[u]=1;//此點已經當過入點for(auto ed:e[u])//對它所有出點進行貪心處理{int v=ed.v,w=ed.w;if(d[v]>d[u]+w)d[v]=d[u]+w;}}
}
void solve()
{cin >> n >> m >> s;//點數、邊數、起點for(int i=0; i<m; i++){cin >> a >> b >> c;e[a].push_back({b,c});}dgi(s);for(int i=1; i<=n; i++) cout << d[i] << ' ';
}

---

優化處理

不難看出，這版代碼一共用了三個for循環，最多嵌套了兩層。時間復雜度極其高，達到了$O(n^2+m)$，所以我們可以對它進行優化處理。

直接跳到時間復雜度最高的地方：找離入點距離最近的出點。如果說此時我們用優先隊列的最小堆來維護距離的話，堆頂的元素就一直是離入點最小的了，這樣我們就省去了去枚舉再遍歷著找的步驟。

實現過程演示

代碼

priority_queue<pii,vector<pii>,greater<pii>> q;
void dji(int s)//當前點
{for(int i=0; i<=n; i++) d[i]=INT_MAX;d[s]=0;q.push({0,s});while(!q.empty()){auto t=q.top(); q.pop();int u=t.se;if(vi[u]) continue;vi[u]=1;for(auto ed:a[u]){int v=ed.fi,w=ed.se;if(d[u]+w<d[v])//當前路到此點距離比之前更優{d[v]=d[u]+w;q.push({d[v],v});}}}
}
void solve()
{cin >> n >> m >> s;//總點數、邊的數量、出發點編號for(int i=0; i<m; i++){int u,v,w;cin >> u >> v >> w;a[u].push_back({v,w});}dji(s);for(int i=1; i<=n; i++) cout << d[i] << ' ';
}

---

例題演示

下面看一道類似的例題：B-代價轉移

思路

雖然此題看著并沒有圖，但是Djikstra算法該有的東西此題都能對應上

• 代價C1,C2,C3看作操作的距離
• 目前的點就是入點，三種操作之后的數分別代表三個出點
• 如果a更大的話直接相減就行

代碼

void dji()
{fill(v,v+N,0);//多實例重置數組fill(k,k+N,INF);//賦值priority_queue<pii,vector<pii>,greater<pii>> q;k[a]=0;//由于要從此點開始，所以設為0q.push({0,a});//將起點入隊maxx=b*2;//所有數中最大可能值,用于邊界判斷while(!q.empty()){auto [val,num]=q.top();//將當前點之前的值取出來（之前是出點）q.pop();if(v[num]) continue;//此值當過入點，跳過v[num]=1;//此時它是入點，標記pii cu[]={{num+1,c1},{num-1,c2},{num*2,c3}};//當前可以到的點for(auto [x,y]:cu){if(x<1||x>maxx) continue;//邊界處理if(k[num]+y<k[x])//如果此時的選擇比它之前的更優{k[x]=k[num]+y;//賦值、入隊q.push({k[x],x});}}}cout << k[b] << endl;
}
void solve()
{cin >> a >> b >> c1 >> c2 >> c3;if(a>=b)//b小的話就只能減了{cout << (a-b)*c2 << endl;return ;}dji();
}

---

之前沒學的時候總覺得這算法光聽名字就很高級，應該還很難。其實它就是一套比較成體系的貪心思想，將圖畫出來進行演示的話還是比較好理解的。