最短路-白红宇

最短路

阅读量：7244 次

发布时间：2019-06-29

本文共 2464 字，大约阅读时间需要 8 分钟。

//orz...高中的时候苦练最短路，然而那年noip没有考。再次写起来倍感亲切啊。

//先整理一波最短路的知识。

一、存图方式

1.邻接矩阵

顾名思义，就是以矩阵的方式来存图啦。有n个点，那么图就是map[n][n]啦。

2.邻接表

和邻接矩阵不同。邻接表是用两点之间的关系来存图的。比如有一条路是x-->y，那么就是在下标为x的数组里插入y，表示存在一条路是x-->y。第一次cpp的邻接表学到了一波新操作。

1 //代码来源：hdoj27222 //建立邻接表3 struct point{4     int v,num;5     point(int a,int b){num=a;v=b;}6 };7 vector
     
       S[maxn*maxn];

ps.第一次用cpp的vector有点点激动。真鸡儿好用啊orz

3.边集数组+链式前向星

（留坑，有点忘了）

二、最短路算法

1.单源最短路—dijkstra

求一个图中两个点之间最短距离的最快的一种方法，要求路径的花费不能有负的。

时间复杂度：O(ElogE)

（大佬们的代码姿势学不来，继续我P式代码风格）

1 //dijk+邻接矩阵 2 void dijk(int st){ 3     memset(V,0,sizeof(V)); 4     V[st]=1; 5     for (int i=1;i<=n;i++) F[i]=A[st][i]; 6     F[st]=Inf; 7     for (int i=1;i<=n;i++){ 8         int k=st; 9         for (int j=1;j<=n;j++){10             if (!V[j] && F[j]
     
      F[k]+A[k][j] && !V[j]) F[j]=F[k]+A[k][j]; 15         }16     }17 }

2.单源最短路—spfa

代码量较小，速度又不错，经常与其他算法组合出现，可以用来判断负环。（突然想起来没练判负环的题）

1 //spfa+邻接矩阵 2 void spfa(int st){ 3     queue
     
       Q; 4     memset(V,0,sizeof(V)); 5     V[st]=1;F[st]=0;T[st]=0; 6     Q.push(st); 7     while (!Q.empty()){ 8         int pos=Q.front(); 9         Q.pop();10         V[pos]=0;11         for (int i=1;i<=n;i++){12             int temp=F[pos]+A[pos][i];13             if (temp
      
       T[pos]+B[pos][i]){22                 T[i]=T[pos]+B[pos][i];23                 if (!V[i]){24                     Q.push(i);25                     V[i]=1;26                 }27             }28         }29     }30 }

1 //spfa+邻接表 2 void spfa(){ 3     queue
     
       Q; 4     for (int i=1;i<=(n+1)*(m+1);i++) F[i]=Inf; 5     memset(V,0,sizeof(V)); 6     F[1]=0; 7     V[1]=1; 8     Q.push(1); 9     while (!Q.empty()){10         int pos=Q.front();11         Q.pop();12         V[pos]=0;13         for (int i=0;i

（留坑，spfa+链式前向星）

3.多元最短路—floyd

经常做预处理用，能处理出来图中任意两个点之间的最短距离，时间复杂度O(n^3) 。

1 //floyd+邻接矩阵 2 void floyd(){ 3     for (int k=1;k<=n;k++){ 4         for (int i=1;i

4.bell-man

1 bool bellman_ford(int s){ 2     queue
     
       Q; 3     memset(inq,0,sizeof(0)); 4     memset(cnt,0,sizeof(cnt)); 5     for (int i=0;i
      
       d[u]+e.dist){16                 d[e.to]=d[u]+e.dist;17                 p[e.to]=G[u][i];18                 if (!inq[e.to]){19                     Q.push(e.to);20                     inq[e.to]=1;21                     if (++cnt[e.to]>n) return 0;22                 }23             }24         }25     }26 }