时间复杂度为：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;
}
