- 【用途】給定一張有向圖，找出起點與終點(或其它頂點)之間的最短路徑。
- 【條件】沒有負權重的邊。
- 【原理】Greedy + DP
- 如果存在一條邊 【s –> t】，權重為 w，則從【起點 –> t】的最短路徑可以透過【起點 –> s】+ 【s –> t】 來拓展。
- 每次都利用已經確定最短距離的頂點來拓展到其相鄰的頂點。
- 如果dis[s] + w 比 dis[t] 小，則更新【起點 –> t】的距離成 dis[t] = dis[s] + w。
- 持續拓展每條邊，直到所有的 dis[x] 都代表【起點 –> x】的最短距離。
- 每條邊只會被拓展一次。
- 【實作】
- vector<pair<int, int> >：存圖。first是「下一個頂點」的編號，second是連結「下一個頂點」的邊的權重，。
- 陣列dis[ ]：用來更新起點到各頂點的最短距離。
- #define P pair<long long, int>
- 【方法1】priority_queue<P, vector<P>, greater<P> > 儲存尚未拓展的頂點，first是起點到「鄰接頂點」的最短距離，second是「鄰接頂點」的編號。使用greater來對first進行由小到大的排序。
- 【方法2】set<P> 儲存尚未拓展的頂點，first是起點到「鄰接頂點」的最短距離，second是「鄰接頂點」的編號。 (st.erase可縮減查找的時間。)
- Line-19：避免走訪已經處理過的頂點。
- 【時間複雜度】O( E * log (V) )，其中V為圖的頂點個數，E是邊數。
- 【範例】UVa 10986 – Sending email
【方法1】priority_queue
// Dijkstra - priority_queue
memset(dist, 0x3F, sizeof(dist));
priority_queue<P, vector<P>, greater<P> > pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()){
P p = pq.top();
pq.pop();
if (dist[p.S] < p.F) continue;
for (auto nxt: G[p.S]){
if (dist[nxt.F] > dist[p.S] + nxt.S){
dist[nxt.F] = dist[p.S] + nxt.S;
pq.push({dist[nxt.F], nxt.F});
}
}
}
【方法2】set
// Dijkstra - set
memset(dist, 0x3F, sizeof(dist));
set<P> st;
dist[S] = 0;
st.insert({0, S});
while (!st.empty()){
P p = *st.begin();
st.erase(p);
if (dist[p.S] < p.F) continue;
for (auto nxt : G[p.S]){
long long new_dist = p.F + nxt.S;
if (new_dist < dist[nxt.F]){
//st.erase({dist[nxt.F], nxt.F});
dist[nxt.F] = new_dist;
st.insert({dist[nxt.F], nxt.F});
}
}
}