目录
Dijkstra迪杰斯特拉算法
迪杰斯特拉算法(Dijkstra)是由迪杰斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
缺点：在负权图中无法使用(SPFA,Bellman_Ford皆可)
写法
1. 利用邻接表记录下边与边的关系；
2. 建立优先队列，以距离出发点的距离为判断依据；
3.初始化全部为0x3f3f3f3f；
4. BFS，求出最长路径
时间复杂度
朴素写法：O(n^2)
优化写法：O((n+m) logm)
例题
描述
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值(边权小于10000)。
请你求出1号点到n号点的最短距离。如果无法从1号点走到n号点，则输出-1。
输入描述
第一行包含整数n和m(n<=1e5,m<=2e5)。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出描述
输出一个整数，表示1号点到n号点的最短距离
如果路径不存在，则输出-1。
样例
输入用例
3 3
1 2 2
2 3 1
1 3 4输出用例
3写法
本题如果用朴素的dijkstra算法，按O(n^2)算的话，1e5*1e5一定会超时，故用优化算法
上优化后算法
#include<bits/stdc++.h>
using namespace std;
#pragma GCC s
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fast
//优化程序运行效率
void read(int &x) {
x=0;
int flag=1;
char ch=getchar();
for(; ch<'0'||ch>'9';) {
if(ch=='-') flag=-1;
ch=getchar();
}
for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
x=x*flag;
}//快读进行常数优化
const int N=1e5+5;
int dis[N],n,m;
int h[N],nx[N*2],v[N*2],w[N*2],tot;
bool vis[N];
//n*2原型：n*(n-1)=m,n为节点数,m为一个图的最大边数
priority_queue <pair <int,int> ,vector<pair <int,int> >,greater<pair <int,int> > > q;
/*
优先队列大根堆写法：priority_queue < pair<int,int> > q;
优先队列小根堆写法：priority_queue <pair <int,int> ,vector<pair <int,int> >,greater<pair <int,int> > > q;
*/
void add(int x,int y,int z) {
tot++;
v[tot]=y;
w[tot]=z;
nx[tot]=h[x];
h[x]=tot;
}//邻接表记录图的关系
void dijkstra(int x) {
memset(dis,0x3f,sizeof dis);
/*
1. 首先,memset()是按内存地址命名的,故用0x3f;
2. memset()中的0x3f赋完值后,dis[]中的数字是为0x3f3f3f3f,而int的最大值为0x7f7f7f7f,
为了防止两个标记的数组值相加导致爆int,故对半开为0x3f3f3f3f
*/
dis[x]=0;//出发点到出发点的距离是0
q.push({0,x});//放入队列
while(!q.empty()) {//队列为空时代表遍利完成
pair <int,int> tmp;
tmp=q.top();//取得队列的第一位
q.pop();//弹出队列的第一位
vis[tmp.second]=1;//vis标记,防止二次入队,降低时间复杂度
for(int i=h[tmp.second]; i; i=nx[i]) {
if(vis[v[i]]==0/*vis标记检查(==0代表没入队),防止二次入队,降低时间复杂度 */&&dis[v[i]]>dis[tmp.second]+w[i]) {
dis[v[i]]=dis[tmp.second]+w[i];
q.push({dis[v[i]],v[i]});//入队
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//优化程序
read(n);
read(m);
for(int i=1; i<=m; i++) {
int x;
int y;
int z;
read(x);
read(y);
read(z);
add(x,y,z);
}
dijkstra(1);//进行遍历
if(dis[n]==0x3f3f3f3f) cout<<-1;//如果没有被访问证明不联通，故输出-1
else cout<<dis[n];
return 0;
}Spfa算法
SPFA就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决是放弃数组，此时所需时间自然就是指数的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。
缺点：在菊花图(下图)中，时间复杂度飘升至O(mn)(m为边数，n为点数)与Bellman_Ford的时间复杂度相同，也不能无法解决限制变数的问题(Bellman_Ford 可以)
不过在正常情况下时间复杂度为O(km) (在稀疏图中一般小于等于2)
例题
描述
给定一个n个点m条边(n<=1e5,m<=2e5)的有向图，图中可能存在重边和自环，边权绝对值小于104。数据保证图中不存在负权回路。
请你求出1号点到n号点的最短距离。如果无法从1号点走到n号点，则输出-1。
输入描述
第一行包含整数n和m(n<=1e5,m<=2e5)。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出描述
输出一个整数，表示1号点到n号点的最短距离
如果路径不存在，则输出-1。
样例
输入用例
3 3
1 2 1
2 3 2
1 3 1输出用例
1写法
#include<bits/stdc++.h>
using namespace std;
#pragma GCC s
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fast
//优化程序运行效率
void read(int &x) {
x=0;
int flag=1;
char ch=getchar();
for(; ch<'0'||ch>'9';) {
if(ch=='-') flag=-1;
ch=getchar();
}
for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
x=x*flag;
}//快读进行常数优化
const int N=1e5+5;
int dis[N],n,m;
int h[N],nx[N*2],v[N*2],w[N*2],tot;
bool vis[N];
//n*2原型：n*(n-1)=m,n为节点数,m为一个图的最大边数
queue<int>q;
void add(int x,int y,int z) {
tot++;
v[tot]=y;
w[tot]=z;
nx[tot]=h[x];
h[x]=tot;
}//邻接表记录图的关系
void spfa(int x) {
memset(dis,0x3f,sizeof dis);
/*
1. 首先,memset()是按内存地址命名的,故用0x3f;
2. memset()中的0x3f赋完值后,dis[]中的数字是为0x3f3f3f3f,而int的最大值为0x7f7f7f7f,
为了防止两个标记的数组值相加导致爆int,故对半开为0x3f3f3f3f
*/
dis[x]=0;//出发点到出发点的距离是0
q.push(x);//放入队列
vis[x]=1;//vis标记,防止二次入队,降低时间复杂度
while(!q.empty()) {
int tmp=q.front();//取得队列的第一位
q.pop();//弹出队列的第一位
vis[tmp]=0;//vis出队标记
for(int i=h[tmp];i; i=nx[i]) {
if(dis[v[i]]>dis[tmp]+w[i]) {
dis[v[i]]=dis[tmp]+w[i];
if(vis[v[i]]==0) {//vis标记检查(==0代表没入队),防止二次入队,降低时间复杂度
vis[v[i]]=1;//vis入队标记
q.push({v[i]});//入队
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//优化程序
read(n);
read(m);
for(int i=1; i<=m; i++) {
int x;
int y;
int z;
read(x);
read(y);
read(z);
add(x,y,z);
}
spfa(1);
if(dis[n]==0x3f3f3f3f) cout<<-1;//如果没有被访问证明不联通，故输出-1
else cout<<dis[n];
return 0;
}Bellman_Ford算法(贝尔曼-福特算法)
遇到有限制边数的题可采用bellman_ford，从起点开始，每一次循环只更新一次，更新出新的最小值。
时间复杂度为O(nm)。
写法
如果只使用一个dis数组进行存储的话 ，在面对下图的时候，会更新多个节点，这不满足我们的需要。
而为了解决此问题，我们建立了一个dis_old数组进行存储，将dis数组第i轮的操作后得到的值，完整复制到dis_old数组，用此数组和dis数组进行处理，就可以避免一次循环更新多个节点的问题了。
下图为dis数组和dis_old数组用上图样例进行更新时候的过程。
| —— | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| tmp | ∞ | ∞ | ∞ | ∞ | ∞ |
| dis | 0 | ∞ | ∞ | ∞ | ∞ |
| —— | —— | —— | —— | —— | —— |
| tmp | 0 | ∞ | ∞ | ∞ | ∞ |
| dis | 0 | 1 | ∞ | ∞ | ∞ |
| —— | —— | —— | —— | —— | —— |
| tmp | 0 | 1 | ∞ | ∞ | ∞ |
| dis | 0 | 1 | 3 | ∞ | ∞ |
| —— | —— | —— | —— | —— | —— |
| tmp | 0 | 1 | 3 | ∞ | ∞ |
| dis | 0 | 1 | 3 | 6 | ∞ |
| —— | —— | —— | —— | —— | —— |
| tmp | 0 | 1 | 3 | 6 | ∞ |
| dis | 0 | 1 | 3 | 6 | 10 |
| —— | —— | —— | —— | —— | —— |
例题
描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
输入描述
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x
到点 y 的有向边，边长为 z。
点的编号为 1∼n。
输出描述
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
样例
输入样例
3 3 1
1 2 1
2 3 1
1 3 3输出样例
3写法
#include<bits/stdc++.h>
using namespace std;
#pragma GCC s
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fast
//优化程序
void read(int &x) {
x=0;
int flag=1;
char ch=getchar();
for(; ch<'0'||ch>'9';) {
if(ch=='-') flag=-1;
ch=getchar();
}
for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
x=x*flag;
}//快读进行常数优化
int n,m,k,dis[505],tmp[505];//俩数组,用来记录和复制
struct node {
int x;
int y;
int z;
} t[10005];//记录边的两顶点,边权
void bellman_ford(int x) {
memset(dis,0x3f,sizeof(dis));
/*
优先队列大根堆写法：priority_queue < pair<int,int> > q;
优先队列小根堆写法：priority_queue <pair <int,int> ,vector<pair <int,int> >,greater<pair <int,int> > > q;
*/
dis[x]=0;//出发点到出发点的距离是0
for(int i=0; i<k; i++) {//模拟边数
memcpy(tmp,dis,sizeof(tmp));//复制数组
for(int j=1; j<=m; j++) {//枚举边
int x=t[j].x;
int y=t[j].y;
int w=t[j].z;
dis[y]=min(dis[y],tmp[x]+w);//找最小值
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//优化程序
read(n);
read(m);
read(k);
for(int i=1; i<=m; i++) {
read(t[i].x);
read(t[i].y);
read(t[i].z);
}
bellman_ford(1);
if(dis[n]>=0x3f3f3f3f/2) cout<<"impossible";
/*
由于负边权的存在初始化的值可能被减小
但题目中负边权的值一般不会小于 -5e8,故用 dis[n]>=0x3f3f3f3f/2
*/
else cout<<dis[n];
return 0;
}