前言
首先，单源最短路径问题(Single Source Shortest Path , SSSP 问题)是说： 给定一张有向图 G= （V,E） ，V 是这个图的点集， E = 是边集， 节点以【1，n】 之间的连续整数编号，(x,y,z) 描述一条从 x 出发 ， 达到 y ，长度(权值)为z 的有向边。设1号点为起点，求长度为n的数组dist ，其中 dist[i] 代表从起点1到节点 i 的最短距离
算法流程
1 初始化dist[1] = 0 , 其余节点的dist值为无穷大
2 找出一个未被标记的 , dist[x]的最小的节点x， 然后标记节点x
3. 扫描节点 x (其上) 的所有出边（x,y,z） 若 dist[y] > dist[x]+ z , 则使用dist[x] + z 更新 dist[y];
4. 重复上述 2~3 步骤，知道所有节点都被标记。
整个dijkstra() 基于贪心思想(由局部最优解得出全局最优), 但它只能适用于所有边的长度(权值)都是非负数的图 ，当边长z都是非负数时，全局最小值不可能再被其他节点更新， 故在第一步中选出的节点 x 必定满足：dist[x] 已经是起点到x的最短路径 。 我们不断选择全局最小值进行标记和扩展，最终课得到起点1 到每个 节点的最短路径的长度。 注：倘若边权出现负数， 那么依照贪心思想， 局部最优的特点 ， 我们最终是用dijkstra所得的局部最优，并不能满足全局最优 ，由此贪心证明失败，算法错误！（解决带有负权边的图可使用bellman-ford或者 spfa(相当于队列优化版本的bellman-ford)，这里只介绍dijkstra算法一种，后续会更新其他算法）
上代码！！！
首先说明，dijkstra有两种不同的实现方法，一个是无优化版的和一个队列优化版的。
说明了具体思路 再来用代码来讲讲这两种实现方式：
无优化版本的dijkstra() O(n*n)
int dijsktra() { // 先将dist 初始化为无穷大 ， memset方法大家自行百度 memset(d,0x3f,sizeof d); // 对应第一步 ， 将 d[1] 赋为 0 d[1]= 0;for(int i=0;i<n-1;i++) { // 遍历n-1次int t= 0;for(int j=1;j<=n;j++) {// 对应第二步 ， 通过遍历所有带你 ， 找出 x if(!st[j] && (!t || d[t]>d[j])) t = j; }// 也对应第二步 标记 xst[t] = 1;// 对应第三步 ， 扫描出边，同时用 x 对所有边更新for(int k=1;k<=n;k++) {d[k] = min(d[k],d[t]+g[t][k]);}}}
上面程序的时间复杂度为 O(n*n) , 主要瓶颈在于第一步的寻找全局最小的过程。
队列优化版本 O(mlogn)
typedef pair<int,int> PII;int n,m;int e[N],ne[N],h[N],w[N],idx;int d[N],st[N];// 领接表 ， 使用数组模拟链表， 具体可看我关于数组模拟链表的文章void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}int dijsktra() {// 使用优先队列priority_queue<PII,vector<PII> , greater<PII>> q;// 对应第一步 初始化所有dist ， 并令 d[1] = 0memset(d,0x3f,sizeof d);d[1] = 0;// c++ 优先队列默认以pair中的first为排序项 first对应边长(权值) ， second对应其边q.push({0,1});while(q.size()) {// 找到当前最短的边 x\u 第二步auto u = q.top();q.pop();// 定义当前 点的 边int ver = u.y;if(st[ver]) continue; // 如果已经被选过了 相当于已经被标记了 ， 就跳过// 标记当前这个边st[ver] = 1;// 因为使用的是领接表存储方式 ， 在这里便对领接表进行遍历 h初始化为 -1 // 由 当前最短的边(相当于 x) 对所有出边进行更新 对应第三步for(int i=h[ver];i!=-1;i=ne[i]) {int j = e[i];if(d[j]>d[ver]+w[i]) {d[j] = d[ver] + w[i];q.push({d[j],j});}}}}
典例示范
849. Dijkstra求最短路 I - AcWing题库
ac代码
#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int N = 510;int n,m;int a,b,c;int g[N][N],d[N],st[N];int dijsktra() {memset(d,0x3f,sizeof d);d[1]= 0;for(int i=0;i<n-1;i++) {int t= 0;for(int j=1;j<=n;j++) {if(!st[j] && (!t || d[t]>d[j])) t = j;}st[t] = 1;for(int k=1;k<=n;k++) {d[k] = min(d[k],d[t]+g[t][k]);}}if(d[n]==0x3f3f3f3f) return 0;return d[n];}int main() {cin>>n>>m;memset(g,0x3f,sizeof g);while(m--) {scanf("%d%d%d",&a,&b,&c);// 使用领接矩阵存储g[a][b] = min(g[a][b],c);}int t = dijsktra();if(!t) cout<<"-1";else cout<<t;return 0;}
850. Dijkstra求最短路 II - AcWing题库
ac代码
#include<iostream>#include<cstring>#include<cstdio>#include<queue>#define x first #define y secondusing namespace std;typedef pair<int,int> PII;const int N = 150010;int n,m;int e[N],ne[N],h[N],w[N],idx;int d[N],st[N];void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}int dijsktra() {priority_queue<PII,vector<PII> , greater<PII>> q;memset(d,0x3f,sizeof d);d[1] = 0;q.push({0,1});while(q.size()) {auto u = q.top();q.pop();int ver = u.y;if(st[ver]) continue;st[ver] = 1;for(int i=h[ver];i!=-1;i=ne[i]) {int j = e[i];if(d[j]>d[ver]+w[i]) {d[j] = d[ver] + w[i];q.push({d[j],j});}}}if(d[n]>=0x3f3f3f3f) return 0;return d[n];}int main() {cin>>n>>m;memset(h,-1,sizeof h);while(m--) {int a,b,c;cin>>a>>b>>c;// 使用领接表存储元素add(a,b,c);}int t = dijsktra();if(!t) cout<<"-1";else cout<<t;return 0 ;}
结言
纯纯的算法萌新 ， 学习ing ， 如有差错 ，请各位大佬多多指教
