最短路问题精选
题单介绍
### 最短路问题解法
**一、Floyd算法：**
Floyd算法只有五行代码，代码简单，三个for循环就可以解决问题，所以它的时间复杂度为O(n*n*n)，可以求多源最短路问题。
Floyd算法可以处理带有负权边，但不能处理带有“负权回路”的图。
核心代码：
```
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
}
```
**二、Dijkstra算法（单源最短路）：**
Dijkstra算法-单源最短路，以一个顶点出发到所有点的最短路。
（复杂度n*n）
算法基本思想：
每次找到离源点最近的顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
我对这个算法的理解就是依次找到离源点最近的顶点跟每个点到源点的距离，然后每个点到源点的距离与离源点最近的顶点 加上两顶点的距离 分别比较。就是dis[v]=dis[u]+e[u][v]。
完整代码：
```
#include<stdio.h>
#include<string.h>
#define inf 99999999
int main()
{
int map[110][110],book[110],dis[110];
int i,j,k,a,b,c,u,min,n,m;
memset(book,0,sizeof(book));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=inf;
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=c;
}
for(i=1;i<=n;i++)
dis[i]=map[1][i];
book[1]=1;
for(i=1;i<=n-1;i++)
{
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0&&dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(k=1;k<=n;k++)
{
if(book[k]==0&&dis[k]>dis[u]+map[u][k])
dis[k]=dis[u]+map[u][k];
}
}
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
｝
```
**三、Bellman-Ford（解决负权边）：**
Dijkstra算法虽好，但是它不能解决带有负权边的图。
算法基本思想：
Bellman-Ford算法最多有n-1个阶段。在每一个阶段，我们对每一条边都要执行松弛操作。其实每实施一次松弛操作，就会有一些顶点已经求得其最短路，即这些顶点的最短路的“估计值”变为“确定值”。此后这些顶点的最短路的值就会一直保持不变，不再受松弛操作的影响。
时间复杂度是（n*m）
适用条件&范围：
单源最短路径;
有向图&无向图;
边权可正可负(如有负权回路输出错误提示);
核心代码：
```
for(k=1;k<=n-1;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(dis[v[i]]>dis[u[i]]+w[i])
dis[v[i]]=dis[u[i]]+w[i];
}
```
**四、SPFA算法：**
SPFA其实就是使用队列优化的Bellman-Ford算法。
SPFA算法在形式上和广度优先搜索非常类似，不同的是在广度优先搜索的时候一个顶点出队后通常就不会再重新进入队列。而这里一个顶点很可能再出队列之后再次被放入队列，也就是当一个顶点的最短路程估计值变小之后，需要对其所有边进行松弛，但是如果这个顶点的最短路程估计值再次变小，仍需要对其所有边再次进行松弛，这样才能保证相邻顶点的最短路程估计值同时更新。
算法基本思想：
初始时将源点加入队列，每次队首（head）取出一个顶点，并对与其相邻的所有顶点进行松弛尝试，若某个点松弛成功，且这个相邻的顶点不在队列中，则将他加入到队列中，对当前顶点处理完毕后立即出队，并对下一个新队首进行如上操作，直到队列为空时算法结束。这里用一个book数组来记录每个顶点是否在队列中。
完整代码：
```
#include<stdio.h>
#define inf 99999999
int main()
{
int u[8],v[8],w[8],first[6],next[8];
int dis[6],book[6],que[101]={0};
int n,m,i,j,k,head=1,tail=1;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
dis[i]=inf;
dis[1]=0;
for(i=1;i<=n;i++)
book[i]=0;
for(i=1;i<=n;i++)
first[i]=-1;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
next[i]=first[u[i]];
first[u[i]]=i;
}
//1号顶点入队
que[tail]=1;
tail++;
book[1]=1;
while(head<tail)
{
k=first[que[head]];
while(k!=-1)
{
if(dis[v[k]]>dis[u[k]]+w[k])
{
dis[v[k]]=dis[u[k]]+w[k];
if(book[k]==0)
{
que[tail]=v[k];
tail++;
book[v[k]]=1;
}
}
k=next[k];
}
book[que[head]]=0;
head++;
}
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
```