图论算法总结之三：最短路径算法
三、最短路径算法
对于带权值的图，从一点到另外一点的权值和（距离和）最小是多少，最短路径算法讨论的就是这样的问题提前说一句，负权值的回路是没有最短路的，因为每绕一圈最短路都会减少
也补一句，所谓最短路径的最优子结构，就是说设s[i][j]是从i到j的权值和，当s[i][j]最小的时候记为p[i][j]，那么这条路所经过的k,满足p[i][j]=p[i][k]+p[k][j],（注意k在i->j的路径上，这一点很重要，很多博客举a地到b地的最短距就是a地到c地的最短距加上c地到b地的最短距都是很明显的错误说法，想想三角形的三边。。。）用反证法是很容易证明的
1.Floyd-Warshall
①思路：对于两点之间的最短路，存在经过某一点中转和不经过该点中转两种选择，我们通过对这两种做法的选择判断来更新已有的最短路，当所有的情况都分析过之后，留下的便是最短路
②实现：用dis[num][num]存最短路，一开始dis里面存的都是初始化时得到的权值，先看所有的最短距用第0个节点中转是否会产生更小的距离（比如第i个节点到第j个节点dis[i][j]?dis[i][0]+dis[0][j]），更小的话，就更新；再看第1个节点，这个时候直接如法炮制，在上一次处理过的矩阵上重复操作（dis[i][j]?dis[i][1]+dis[1][j]）即可；在之后以此类推，直到每一个点作为中转的情况都考虑到，得到的就是最短路
③说明：为什么可以在之前更新过的矩阵上直接开始下一轮更新？比如dis[i][1]+dis[1][j]，在讨论是否i->1->j比i->j更好的时候，其实i->0->1 and i->1 ; 1->0->j and 1->j孰大孰小我们已经判断过了，这样对于i->j的最短路可能情况，在我们已经讨论的中转点里（0 和1）里面我们只用讨论1了，之后的分析以此类推，可以说明这样做的正确性
④代码：
int dis[num][num],G[num][num];
int main(){
//省略输入数据初始化图矩阵的过程
for(int i=0;i<num;i++)
for(int j=0;j<num;j++)
dis[i][j]=G[i][j];
//Floyd
for(int k=0;k<num;k++){//枚举中转点
for(int i=0;i<num;i++){//这两重循环是更新最短距的
for(int j=0;j<num;j++){
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
return 0;
} ⑤时间复杂度：三种循环，假设点数是N，时间复杂度为O（N^3）
⑥局限性：虽然实现容易，时间复杂度太大
2.Dijkstra
假设一个图里面没有负权边，固定一个起点讨论最短路问题
①思路：对于最短距还没有确定的节点，当前估计距离最小的那一个实际上也就是最短距可以确定的那一个，以之更新其余点的最短距（dis[i]?dis[u]+G[u][i]），然后挑选其余点中的最短距最小的那一个设定为最短距确定的节点，以此类推便可以完成任务；为了方便说明，我们设所有最短距已经确定了的点的集合是P，与之相对还没确定的点集是Q，Q+P=V
②说明：为什么当前最短距估计值最小的节点就是最短距确定的节点？首先，第一次将起点选出的正确性是不用质疑的；然后，利用反证法，假设找到u节点，u的最短路估计值最小，但估计值还不是确定的最短路值，那么一定存在另一条路径s->u，假设该路径上的第一个在P里面的点是x（x至少也可以是s），x的后驱是y（y也有可能就是u），那么由于s->u按照我们的算法，是当前最短距估计值最小的一个，那么s->y就不可能小于s->u，那么这种方案下的s->x->y->u就不可能比s->u还小，也就是说找不到其他路径小于当前的s->u，这就与我们的假设矛盾，所以s->u是确定的最短距
③实现：
book[num]记录每一个节点是否加入P，一开始都设为0，加入之后就设置为1；
对于所有还没有加入P的节点，选出dis[i]最小的那一个，加入P，然后用i做中转松弛i所连接的所有边；
以此类推，一共要加入num-1个点到P，最后一个点可以不看了，因为之前，所有可以松弛其的点，都已经对其松弛过了
④代码与复杂度分析：
（1）邻接矩阵：找min为O(N),每一个min遍历边为O(N),一共就是O（N^2）
const int INF=1<<29;
int dis[num],book[num],G[num][num];//G里面可能有INF权值的边
int main(){
//省略输入数据初始化图矩阵的过程
memset(book,0,sizeof(book));
for(int i=1;i<=num;i++){
dis[i]=G[1][i];
}
//Dijkstra
for(int i=1;i<=num-1;i++){//一共要往P里面加入num-1个节点
int min=INF+1,u;//min初始化为INF+1是为了解决当前估计值全部为INF的情况，这种情况下，图就不是连通图了，而是森林
for(int j=1;j<=num;j++){//找到当前估计值最小的节点
if(book[j]==0&&dis[j]<min){
min=dis[j];
u=j;
}
}
book[u]=1;
for(int j=1;j<=n;j++){//松弛操作，当然只用松弛那些还不在P里面的点的估计值
if(book[j]==0&&dis[j]>dis[u]+G[u][j]){
dis[j]=dis[u]+G[u][j]
}
}
}
return 0;
} （2）用邻接表+优先队列进行的优化
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int num=100;//最大节点数
const int INF=1<<29;
int n;//节点数
int d[num+10];
/*struct vertax{
int id,dis;
vertax(int id,int dis):id(id),dis(dis){}
bool operator < (const vertax &v){
return id<v.id;
}
};*/
typedef pair<int,int> V; //first是最短距离，second是顶点的编号,按first排序
struct edge{
int to,cost;
edge(int to,int cost):to(to),cost(cost){}
};
vector<edge> G[num+10];
void Dijkstra(int s){
priority_queue<V,vector<V>,greater<V> > q;
for(int i=1;i<=num;i++){
d[i]=INF;
}
d[s]=0;
q.push(V(0,s));
while(!q.empty()){
V v=q.top();q.pop();
int id=v.second,dis=v.first;
if(dis>d[id])continue;
for(int i=0;i<G[id].size();i++){
edge e=G[id][i];
if(d[e.to]>d[id]+e.cost){
d[e.to]=d[id]+e.cost;
q.push(V(d[e.to],e.to));
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){//输入图
int m,t,val;
cin>>m;
for(int j=1;j<=m;j++){
cin>>t>>val;
edge e(t,val);
G[i].push_back(e);
}
}
int s;cin>>s;//起点
Dijkstra(s);
for(int i=1;i<=n;i++){
cout<<d[i]<<' ';
}
cout<<endl;
return 0;
} 3.Bellman-Ford
①思路：松弛这个操作的意义是什么？即判断一个节点是否可以作为中转，或一条边是否可以作为桥梁。使用所有的边对所有的最短距进行一次松弛，即允许每一个点可以由从起点出发的至多一条边到达；如果此时再进行一次同样的操作，那么就相当于允许最多经过两条边到达，以此类推；直到所有节点的最短距都不再发生改变，即得到了答案
②分析：
最多需要几轮这样的操作？答案是n-1轮。因为不可能有环的出现，如果是正权环，可以去掉，最短路更小；如果有负权环，那么最短距不存在。所以如果最短距存在的话，n-1轮（n个节点连在一起正好n-1条边）之后所有的点的最短距都不会再更新了，不过如果试了第n轮，发现有最短距改变了，那便可以断言：一定有负权环；
再思考一下，对于一个节点而言，它的最短距可能是需要允许至少k条边经过的，那么如果我试到了k+1，k+2……条边的话，就肯定不会再改变了，那么这样再去尝试就十分浪费，一个稍微粗糙一点的改进方法就是：如果所有的节点的最短距都不发生改变的话，那么就不用一直试到n-1轮了，直接退出就好
③实现：用所有边更新所有点，重复n-1轮，两重循环就可以搞定，由于我们的对象是边，不如就用三个数组u[num],v[num],w[num]来存储第i条边的起点，终点和权值。最短距和Dijkstra一样用dis[num],更新就用dis[v[i]]?dis[u[i]]+w[i]，注意监测一轮是否有至少一次更新，如果没有，就结束循环
④代码：
#include<iostream>
using namespace std;
const int num=100;
const int INF=1<<29;
int n;int m;
int u[num+10],v[num+10],w[num+10];
int dis[num+10];
void BF(int s){
for(int i=1;i<=n-1;i++){
int is_renew=0;
for(int j=1;j<=m;j++){
if(dis[v[j]]>dis[u[j]]+w[j]){
dis[v[j]]=dis[u[j]]+w[j];
is_renew=1;
}
}
if(is_renew==0)break;
}
}
int main(){
cin>>n;
cin>>m;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
dis[i]=INF;
}
int s;cin>>s;
dis[s]=0;
BF(s);
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
return 0;
}⑤时间复杂度：
一共n-1轮，每轮有m条边处理，复杂度就是O(|V|*|E|)
4.队列优化的BF
上面有一个遗留的问题，就是我们虽然给出了一个小小的优化，但是太粗糙，可以想见在第一轮结束的时候，就开始有点的最短距不会再被更新了，为什么一定要到所有的点都不再被更新时才停止更新呢，明明只要有点开始不更新了，那么这个点就不用再试了，但是还是有一个问题，那就是有的边可能在前几轮不被更新，后面允许经过的边多起来了，就开始被更新，那么这时要统一设定一个标准来判断谁已经不会再被更新就有些麻烦，我们采用新的思路
①思路：一个点如果经过一次松弛没有被更新，那么它就是已经确定最短路的点，那么它所连边都无需再考虑尝试松弛，因为从起点到该点的距离信息并没有改变，（当然其所在路径上的所有点也不可能被改变，因为我们知道最短路径具有最有子结构，这些路径上的点都是不会再被更新的点）再用没变化的dis[u[i]]+w[i]去判断一个已经更新过的dis[v[i]],就是一种浪费；简而言之就是只使用最短距被成功更新的点的所连边，去进行松弛判断
②实现与说明：
利用队列，把被成功更新的节点放入队尾，从队头取节点用相邻边进行松弛，操作完之后出队；注意，一个点k没有必要同时在一个队列里面出现两次及以上，考虑此时要加入的k在对立面已经有了一个，那么我们加入k的初衷就是因为k的最短距缩小了，最好在之后进行一次对k所连边的松弛操作，那么已经存在于队列中的那个k也是基于相似的目的，只是这个目的还没有被实现就已经将k的最短距又一次优化了，那么就使用这最先加入的一个k两次目的一起实现不就好了么
所以标记数组应该格外小心使用，k加入队列，则标记为1，从队头出队以后，立刻标记为0，这也可以看出一个节点是可以反复进入队列的，也就是说一个节点是可以多次被成功松弛的，一次成功的松弛就是多经过一条边，一开始都设置为INF，就是零条边，那么要是进入队列达到了n次及以上就说明存在负权环
③代码：
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int num=100;
const int INF=1<<29;
int dis[num+10];
int is_join[num+10];
struct edge{
int to,cost;
edge(int to,int cost):to(to),cost(cost){}
};
vector<edge> G[num+10];
void BF(int s){
memset(is_join,0,sizeof(is_join));
queue<int> q;
q.push(s);is_join[s]=1;
while(!q.empty()){
int v=q.front();q.pop();is_join[v]=0;
for(int i=0;i<G[v].size();i++){
edge e=G[v][i];
if(dis[e.to]>dis[v]+e.cost){
dis[e.to]=dis[v]+e.cost;
q.push(e.to);
is_join[e.to]=1;
}
}
}
}
int main(){
int n;cin>>n;
int m;cin>>m;
int u,v,w;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
edge e(v,w);
G[u].push_back(e);
}
int s;cin>>s;
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[s]=0;
BF(s);
for(int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
return 0;
}5.总结