時間復雜度為：O((n+m)logn)
算法特點：非負邊權、單源最短路、頂點數、邊數<1000000，數據結構前置：領接表、哈希表、二叉堆
算法：
第一步，建圖，任何算法我們都要去思考，用什么數據結構來存儲，這個算法我們采用鄰接表來存儲，有時候輸入數據，并不是我們期待的那樣，所以需要對圖進行一些處理，這就是建圖的過程
第二步，輔助數組，對于圖G = <V, E>，源點為s，dist[i]表示s到i的最短路，visited[i] 表示dist[i]是否已經確定（布爾值），即s到i的最短路，是否已經確定。
第三步，輔助堆，利用一個小頂堆heap存放二元組（v, dist[v]），小頂堆扮演的是優先隊列作用，dist[v]值越小的，會從優先隊列中優先出列。
第四步，初始化，初始化所有頂點的數據見下，
dist[i] = 無窮大（0 =< i =< n）
visited[i] = false
dist[s] = 0
heap.push(s, dist[s])
第五步，找距離最小的點，從小頂堆中不斷彈出元素u，并且判斷visited[u]是否為true，如果為true，則繼續彈出；否則標記為true，并且從u出發，進行松弛操作，如果堆為空，算法結束。
第六步，松弛操作，更新從u出發，到達頂點v的最短路dist[v]，
dist[v] = min(dist[v], dist[u] + w(u, v))
代碼分析：第一步，定義距離二元組 Dist(v, w)
第二步，初始化鄰接表
function initEdges(n, edges[maxn])
? for i -> (0, n-1)
? ? edges[i] = {}
第三步，鄰接表加邊，
function addEdge(edges[maxn], u, v, w)
? edges[u].append(Dist(v, w))
第四步，建圖
addEdge(edges, u1, v1, w1)
addEdge(edges, u2, v2, w2)
...
第五步，框架代碼
function DijkstraHeap(n, st, edges[maxn], d[maxn])
? heap = Heap()
? visited[maxn] = false
? dijkstraInit(n, st, heap, visited, d)
? while(not heap.empty())
? ? u = dijkstraFindMin(heap)
? ? dijkstraUpdate(u, edges, heap, visited, d)
第六步，初始化
function dijkstrainit(n, st, heap, visited[maxn][maxn])
? for i->(0, n-1)
? ? d[i] = inf
? ? visited[i] = false
? dist[st] = 0
? heap.push(Dist(st, d[st]))
第七步，獲取最小值
function dijkstraFindMin(heap)
? s = heap.top()
? heap.pop()
? return s.v
第八步，松弛操作
function dijkstraUpdate(u, edges[maxn], heap, visited[maxn], d[maxn])
? if not visited[u]
? ? visited[u] = true
? ? for i-> (0, edges[u].size() - 1)
? ? ? v = edges[u][i].v
? ? ? w = edges[u][i].w
? ? ? if (d[u] + w < d[v])
? ? ? ? ?d[v] = d[u] + w
? ? ? ? ?heap.push(Dist(v, d[v]))
代碼練習，對應藍橋云課 Dijkstra求最短路2 代碼見下
#include <iostream>
#include <vector>
#include <queue>using namespace std;#define inf 1000000001
#define maxn 100001
#define ValueType intstruct Dist{int v;ValueType w;Dist() {}Dist(int _v, ValueType _w): v(_v), w(_w) {}bool operator < (const Dist& d) const{return w > d.w;}
};typedef priority_queue<Dist> Heap;void addEdge(vector<Dist>* edges, int u, int v, ValueType w){edges[u].push_back(Dist(v, w));
}void dijkstraInit(int n, int st, Heap& heap, bool *visited, ValueType* d){for(int i=0; i<n; ++i){d[i] = inf;visited[i] = false;}d[st] = 0;heap.push(Dist(st, d[st]));
}int dijkstraFindMin(Heap& heap){Dist s = heap.top();heap.pop();return s.v;
}void dijkstraUpdate(int u, vector<Dist>* edges, Heap& heap, bool *visited, ValueType* d){if(visited[u]){return;}visited[u] = true;for(int i=0; i<edges[u].size(); ++i){int v = edges[u][i].v;ValueType w = edges[u][i].w;if(d[u] + w < d[v]){d[v] = d[u] + w;heap.push(Dist(v, d[v]));}}
}void DijkstraHeap(int n, int st, vector<Dist>* edges, ValueType* d){Heap heap;bool visited[maxn] = {false};dijkstraInit(n, st, heap, visited, d);while(!heap.empty()){int u = dijkstraFindMin(heap);dijkstraUpdate(u, edges, heap, visited, d);}}vector<Dist> edges[maxn];
ValueType d[maxn];int main()
{int n, m;cin >> n >> m;while(m--){int u, v, w;cin >> u >> v >> w;--u, --v;addEdge(edges, u, v, w);}DijkstraHeap(n, 0, edges, d);if(d[n-1] == inf){cout << -1 << endl;}else{cout << d[n-1] << endl;}// 請在此輸入您的代碼return 0;
}? 代碼練習 2 對應藍橋云課 藍橋王國 代碼見下
#include <iostream>
#include <vector>
#include <queue>using namespace std;#define inf 1000000001000000001
#define maxn 300001
#define ValueType long long struct Dist{int v;ValueType w;Dist() {}Dist(int _v, ValueType _w): v(_v), w(_w) {}bool operator < (const Dist& d) const{return w > d.w;}
};typedef priority_queue<Dist> Heap;void addEdge(vector<Dist>* edges, int u, int v, ValueType w){edges[u].push_back(Dist(v, w));
}void dijkstraInit(int n, int st, Heap& heap, bool *visited, ValueType* d){for(int i=0; i<n; ++i){d[i] = inf;visited[i] = false;}d[st] = 0;heap.push(Dist(st, d[st]));
}int dijkstraFindMin(Heap& heap){Dist s = heap.top();heap.pop();return s.v;
}void dijkstraUpdate(int u, vector<Dist>* edges, Heap& heap, bool *visited, ValueType* d){if(visited[u]){return;}visited[u] = true;for(int i=0; i<edges[u].size(); ++i){int v = edges[u][i].v;ValueType w = edges[u][i].w;if(d[u] + w < d[v]){d[v] = d[u] + w;heap.push(Dist(v, d[v]));}}
}void DijkstraHeap(int n, int st, vector<Dist>* edges, ValueType* d){Heap heap;bool visited[maxn] = {false};dijkstraInit(n, st, heap, visited, d);while(!heap.empty()){int u = dijkstraFindMin(heap);dijkstraUpdate(u, edges, heap, visited, d);}}vector<Dist> edges[maxn];
ValueType d[maxn];int main(){int n, m;cin >> n >> m;for(int i=0; i<m; ++i){int u, v, w;cin >> u >> v >> w;--u, --v;addEdge(edges, u, v, w);}DijkstraHeap(n, 0, edges, d);for(int i=0; i<n; ++i){if(i){cout << " ";}if(d[i] == inf){cout << "-1";}else{cout << d[i];}}cout << endl;return 0;
}
