最短路问题
(其实写完之后才发现有图片的话会更加直观，我也就不用打那么多字了，但是觉得上传图片有点麻烦了，先将脉络mark一下，之后有时间在上传图片)。
最短路问题可以大致分为单源最短路问题，多源最短路问题。
单源最短路问题：
全是正边权：
朴素dijkstra：
基本思路：
首先需要一个集合，用于存储已经确定距离起点最小距离的点。
逻辑就是在遍历每个点，找到在集合外面同时距离起点最近的点，把这个点t放进集合中。然后用这个点来更新其他的点的距离。
时间复杂度是O(n2) .
堆优化版dijkstra
基本思路：
相比于朴素版，在选取t的时候做了一些优化。用的是小根堆进行排列，每次从堆中移除堆头，该店就是t，同时更新与t相邻的点的距离。
时间复杂度是在O(mlogn) .
存在负边权
bell-ford算法：
基本思路：其实就是暴力求解，在存储图的时候，不一定非要是邻接表或者是邻接矩阵。只要可以每一次迭代的时候，可以遍历全部的边就可以。
他的逻辑就是，外层循环直接迭代n次，(n为点的数量)，内层循环迭代m次(m为边的数量)。每次按边的权重差来进行更新，故外层循环n次是一定够的。每一个节点更新与否，取决于他的临点更不更新。
时间复杂度大概是O(mn)
spfa算法
是bell_ford算法的优化版。是根据bellman的纯暴力算法，体现在更新节点严重依赖于前继节点上。所以spfa算法用了一个容器，可以是队列，优先队列，栈，来充当一个集合，用来存储待更新的节点，一旦需要用这个节点来进行更新，就出队就可以了，用false标记一下，然后在把用这个节点更新的其他节点，如果不在队列里面的话，就直接入队，在的话，就不用管他。
时间复杂度是一般是O(m) ,最坏的情况是O(mn) 。
这里就会有一些争议。我最近在网上冲浪看到的，有些比较恶心的出题人，会卡spfa的数据，什么网格图，菊花图什么的。
这种情况一般出现在全是正权边的情况下，负边权的话一般都不会卡，因为只有spfa这种解决方案。所以在正权边的时候，我们需要考虑到底是采用朴素，堆优化的dijkstra，还是用spfa。
还有顺便提一下，并不是朴素的djkstra算法一定差于堆优化版的djkstra算法，这要根据实际情况来。一般来说，我们是稠密图用邻接矩阵来存，然后采用朴素dijkstra算法，相当于是O(m),若此时用heap优化的话，是O(mlogn)。从这种意义来看，朴素版是要比heap版是更优的。
多源最短路问题：
floyd算法
基本思路：其实是基于dp的一种做法，也是极其暴力，三层循环就搞定了。
状态转移方程是f[i] [j] = min(f[i] [k]+ f[k] [j]) ;
下面分别来进行介绍一下各种算法的实际应用：
朴素dijisktra算法
Dijkstra求最短路I
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include
using namespace std ;
const int N = 520 ;
int g[N][N] , dist[N] ;
bool st[N] ;
int n , m ;
void dijkstra()
{
memset(dist , 0x3f , sizeof dist) ;
dist[1] = 0 ;
for(int i = 0 ; i < n ; ++ i)
{
int t = -1 ;
for(int j = 1 ; j <= n ; ++ j) { if(!st[j] && (t="=" -1 || dist[t]> dist[j]))
{
t = j ;
}
}
st[t] = true ;
for(int i = 1 ; i <= n ; ++ i) { dist[i]="min(dist[i]" , dist[t] + g[t][i]) } int main() cin>> n >> m ;
memset(g , 0x3f , sizeof g) ;
while(m--)
{
int a , b , c ;
cin >> a >> b >> c ;
g[a][b] = min(g[a][b] , c) ;
}
dijkstra() ;
if(dist[n] == 0x3f3f3f3f)
cout << -1 << endl ;
else
cout << dist[n] << endl ;
return 0 ;
}
有几个细节点要注意一下。
这里的t==-1，是为了赶紧找到第一个参照。因为t的含义是，在集合外面找一个dist最小的点，并放进集合里面，然后依次来更新其余个点的距离。
一开始，我就有一个疑问，为什么这里的算法，在初始化的时候，g[i] [i]为什么不标零。
其实最好是要标一下的，但是在这个算法当中，唯一用到g的地方，其实是用t来更新的时候。我们假设这样一种情况，
当t == i的时候，dist[i] = min(dist[i] , dist[t] + g[t][i]) ，dist[i] <= dist[i] + g[i] [i]，所以对于这一题其实没有什么影响。
Dijkstra求最短路II
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#include
using namespace std ;
const int N = 1e6 ;
int idx , h[N] ,ne[N] ,e[N],w[N] ;
int dist[N] ;
int n , m ;
typedef pair PII ;
bool st[N] ;
void add(int a , int b , int c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c, h[a] = idx ++ ;
}
int dijkstra()
{
memset (dist , 0x3f , sizeof dist) ;
dist[1] = 0 ;
priority_queue , greater > heap ;
heap.push({0,1}) ;
while(heap.size())
{
PII t = heap.top() ;
heap.pop() ;
int index = t.second ;
int distance = t.first ;
if(st[index])
continue ;
else
st[index] = true ;
for(int i = h[index] ; i != -1 ; i = ne[i])
{
int j = e[i] ;
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i] ;
heap.push({dist[j] , j}) ;
}
}
}
if(dist[n] == 0x3f3f3f3f)
return -1 ;
return dist[n] ;
}
int main()
{
cin >> n >> m ;
memset(h , -1 , sizeof h) ;
while(m--)
{
int a , b , c ;
scanf("%d%d%d",&a,&b,&c) ;
add(a,b,c) ;
}
cout << dijkstra() << endl ;
return 0 ;
}
有边数限制的最短路
给定一个 n个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
#include
using namespace std ;
const int N = 510 , M = 10010 ;
struct edge
{
int a, b ,c ;
}edges[M] ;
int n , m , k;
int dist[N] , backup[N];
void bellman_ford()
{
memset(dist , 0x3f , sizeof dist) ;
dist[1] = 0 ;
for(int i = 0 ; i < k ; ++ i)
{
memcpy(backup , dist , sizeof dist) ;
for(int i = 1; i <= m ; ++ i) { int a="edges[i].a" b="edges[i].b" w="edges[i].c" dist[b]="min(dist[b]" , backup[a] + w) } main() cin>> n >> m >> k;
for(int i = 1 ; i <= m ; ++ i) { int a ,b ,c cin>> a >> b >> c ;
edges[i] = {a , b , c} ;
}
bellman_ford() ;
if(dist[n] > 0x3f3f3f3f / 2)
puts("impossible") ;
else
cout << dist[n] << endl ;
return 0 ;
}
spfa求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
#include
using namespace std ;
const int N = 1e5 + 10 ;
int idx , e[N] ,ne[N] ,h[N] ,w[N] ;
int dist[N] ;
bool st[N] ;
int n , m ;
void add(int a , int b ,int c)
{
e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++ ;
}
void spfa()
{
memset(dist , 0x3f , sizeof dist) ;
dist[1] = 0 ;
queue q ;
q.push(1) ;
st[1] = true ;
while(q.size())
{
int t = q.front() ;
q.pop() ;
st[t] = false ;
for(int i = h[t] ; i != -1 ; i = ne[i])
{
int j = e[i] ;
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i] ;
if(!st[j])
{
q.push(j) ;
st[j] = true ;
}
}
}
}
}
int main()
{
cin >> n >> m ;
memset(h , -1 , sizeof h) ;
while(m--)
{
int a , b , c ;
cin >> a >> b >> c ;
add(a,b,c) ;
}
spfa() ;
if(dist[n] == 0x3f3f3f3f)
puts("impossible") ;
else
cout << dist[n] << endl ;
return 0 ;
}
最后解决一下为什么spfa和bellman_ford算法可以解决负权边的问题。
因为对于dijkstra算法，他是一锤子买卖，之所以不可以解决负的问题我们用图来进行解释。
是因为如图所示，如果按照dijkstra算法的尿性，入集合的顺序是1，2,4,6 ， 但是其实是应该是1,3,5,6.是因为在2与3进行纠结的时候，把2push到了集合里面，之后就不会放出来了。而后续的所有直到所有的节点的距离之和都不会大于1到3的距离，所以说他是一锤子买卖，一旦选定了当时距离起点最近的点之后，就push进集合，不出来了，然后就用这个点来进行更新，所以一旦有负全边，他根本看不见，可以理解为是1到3的距离，直接蒙蔽了dijkstra的眼睛，让他看不见之后的-100的权值。
那我们再来看，bellman_ford，spfa和bellman_ford原理相同，我们就拿bellman_ford做例子。
他是完全暴力，按照边来更新的，不像dijkstra是按点来更新的，所以他每一次迭代，都会重新刷新一遍所有点，取其中最小的边，来进行后继的更新，所以被更新后的点，可以再次被更新，所以他完全可以看见负权边的存在。
Floyd算法求最短路问题
给定一个 n 个点 m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
接下来 k行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,
1≤k≤n2，
1≤m≤20000,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
#include
using namespace std ;
int n , m , k ;
const int N = 210 ;
int g[N][N] ;
void floyd()
{
for(int k = 1; k <= n ; ++ k) { for(int i="1" <="n" i) j="1" j) g[i][j]="min(g[i][j]" , g[i][k] + g[k][j]) } int main() scanf("%d%d%d" &n ,&m,&k) memset(g 0x3f sizeof g) g[i][i]="0" while(m--) a b c scanf("%d%d%d",&a,&b,&c) g[a][b]="min(g[a][b]" c) floyd() while(k--) x,y cin>> x >> y ;
if(g[x][y] > 0x3f3f3f3f / 2)
puts("impossible") ;
else
cout << g[x][y] << endl ;
}
return 0 ;
}
这没有什么好说的，完全是暴力dp，感觉其实和bellman_ford算法有异曲同工之妙。至于原理，之后有时间在推一下。
