最短路径算法
简介
在现实与竞赛中经常会遇到求最短路径的问题，比如求快递员送货的最短路径、两个村庄之间的来往的最短路径等等。一般的，给定n个点及每两个有联系的点之间的距离，在暴力求解的过程中，将每个两个点的所有路径遍历并记录再求自小距离，这样的运算相当耗时，可以得出，时间复杂度约为O(2^N)。很明显，我们需要对其进行优化。
下面介绍的dijkstra算法和SPFA算法将可以很好的解决最短路径问题。
dijkstra算法
这个算法的使用需要给定点按条件能连成不带负权值的图。此算法的思想是基于贪心法，首先，将每两个点之间的距离记录下来，两点之间无直接联系则用无穷大代替其距离，选择一个起点，每次循环开始从剩下的未选取过的点中选取一个与起点距离最近的点并以其为中间点，更新其他所有点到起点的距离，知道所有除起点外的点都被选取过循环结束。由于所有的边权都为正，因而不会出现一个距离更短且没被选取过的点，因而保证了算法的正确性。
算法设计：
1. 将图的所有顶点分为两组，一组为已经计算好距离的顶点，设为A组；另一组为还未计算的顶点，记为B组；初始时，所有顶点放在B组，接着将起点vi放入A组。
2. 从B组中找出离顶点vi最近的点vj（1<=j<=n），将vj加入A组，同时以vj为中间点，更新vi到B组中所有顶点的最短距离。
3. 重复第二个步骤直到所有的点从B组中加入到A组。
算法实现
用flag记录顶点在哪个组。当flag[i]为true时，i顶点在A组，flag[i]为false时，i顶点在B组。用dist[i][j]记录顶点i至顶点j的距离，初始时，有边相连的两个顶点dist[i][j]的值为图上两点的边权值，无边相连的两个点的dist[i][j]值为无穷大；
代码如下：
#include<stdio.h>
const int max=100000;
int dist[max][max];
bool flag[max];
void main(void)
{
int i,j,n,vi;
int tmp1,tmp2,tmp3;
scanf("%d%d",&n,&vi);//读取所求的图的点的个数及起点位置
while(scanf("%d%d%d",&tmp1,&tmp2,&tmp3))//读取两个点之间的距离，tmp3暂存距离
{
dist[tmp1][tmp2]=tmp3;
dist[tmp2][tmp1]=tmp3;
}
for(i=1;i<=n;i++)
flag[i]=false;
for(i=1;i<=n;i++)//初始时构造dist[i,j]
for(j=1;j<=n;j++)
if(!dist[i][j])
dist[i][j]=max;
//计算顶点vi到其他顶点的最短路径
flag[vi]=true;
for(i=2;i<=n;i++)//求另外n-2个顶点
{
tmp1=max;
for(j=1;j<=n;j++)//找出存在于B组且离vi最近的顶点
if(!flag[j]&&dist[vi][j]<tmp1)
{
tmp1=dist[vi][j];//tmp1记录大小，tmp2记录位置
tmp2=j;
}
flag[tmp2]=true;//将选取的点放入A组
for(j=1;j<=n;j++)//以找到的点为中间点更新vi到B组中的顶点的最短距离
if(!flag[j]&&dist[vi][tmp2]+dist[tmp2][j]<dist[vi][j])
dist[vi][j]=dist[vi][tmp2]+dist[tmp2][j];
}
for(i=1;i<=n;i++)
if(i!=vi)
printf("%d: %d\n",i,dist[vi][i]);//输出vi到各顶点的最短距离
}举个例子
输入如图所示的顶点关系： 
（按上述程序输入格式输入）
5 1
1 2 1
1 3 3
1 5 8
2 3 1
2 4 2
3 4 2
4 5 2
end
顶点vi进入A后
A组
| ||||||||||
B组
|
顶点2进入A后
A组
| ||||||||||
B组
|
顶点3进入A后
A组
| ||||||||||
B组
|
顶点4进入A后
A组
| ||||||||||
B组
|
输出结果：
2： 1
3： 2
4： 3
5： 5
此算法的时间复杂度为O(N^2)，可以快速求出某一点到另外任意一点的最短路径，在图不是特别大的情况下非常好用，以上代码及事例均在无向图的条件下，需要的话可以自行更改为有向图。
SPFA算法
在某些图中可能存在权值为负的边，计算最短路径时如果采用Dijkstra算法时，对于存在负环的图将会循环重复计算。
例如有向图
当求1到3号顶点的最短路径时，由于2与3之间存在负环，所以只有第一遍可以得到正确答案，而若再次求1到3的距离时1到2的距离被更新，同时2到3的距离也被更新，得不到正确答案；因而若用Dijkstra算法处理负环时每次循环都会重复更新，也就无法通过多次循环求出任意点到另一点的距离。同时在更新时一个点只会被用作一次的中间点，无法重复更新。
SPFA算法可以解决这个问题，这个算法运用了队列形式，其形式与宽度优先搜索非常相似，将需要扫描的点放进队列，每次从队列中取出一个点作为新的中间点并对所有的点做一次遍历检查是否有更新，如果距离被更新则将被更新的点重新放入队列中，循环运行直到队列被取空。这样做不同于Dijkstra算法的每个点只能用作一次的中间点，被移出队列的点在之后被更新后可能再一次进入队列，其本身被改进后还可以再去改进其他点，这样就可以得到正确的答案。
算法设计：
1. 初始时，把原点s加入到队列中，并使dist[s]为0，其他的点到原点的距离dist[v]均为max。
2. 每次取出队列里的一个元素，将该点设为中间点，对与该点有边相连的点v进行更新距离，如果成功更新距离则改进dist[v]的数值，并把v加入队列中。
3. 重复2，直到队列为空。
假设图中有n个点e条边，用二维数组path[u][v]存储图，dist[v]数组表示各个点到原点s的距离，用flag[v]来表示该顶点是否在队列中；q[]数组存储队列，q[t]为头q[h]为尾；
代码如下：
#include<stdio.h>
const int max=100000;
int dist[max]={0},q[max]={0};
int path[max][max]={0};
bool flag[max];
void main(void)
{
int i,n,e,s,v;
int h,t;//用作记录队列q的头尾的位置，h为尾，t为头
int tmp1,tmp2,tmp3;
scanf("%d%d%d",&n,&e,&s);//读取所求的图的点的个数n、有权值的边的个数e及原点序号s
for(i=1;i<=e;i++)
{
scanf("%d%d%d",&tmp1,&tmp2,&tmp3);//读取两个点之间的距离，tmp3暂存距离
path[tmp1][tmp2]=tmp3;
}
for(i=1;i<=n;i++)
flag[i]=false;
for(i=1;i<=n;i++)//初始时构造dist[v]
dist[i]=max;
dist[s]=0;
//计算顶点s到其他顶点的最短路径
h=0;
t=0;
t++;
q[t]=s;
flag[s]=true;//初始化队列，将原点s放入队列
while(h!=t)
{
h=(h%n)+1;//循环队列
v=q[h];//v为新的中间点
flag[v]=false;//取出队列中的点
for(i=1;i<=n;i++)
if(path[v][i]!=0&&dist[v]+path[v][i]<dist[i])
{
dist[i]=dist[v]+path[v][i];
if(!flag[i])//如果被更新的点不在队列中则加入进队列
{
t=(t%n)+1;
q[t]=i;
flag[i]=true;
}
}
}
for(i=1;i<=n;i++)
if(i!=s)
printf("%d: %d\n",i,dist[i]);//输出s到各顶点的最短距离
}举个例子
输入如上图所示的数据
初始时原点为s=1放入队列q
Dist
| ||||||||
队列q
|
第二次while时2，3号入队。
Dist
| ||||||||
队列q
|
第三次2出队4入队
Dist
| ||||||||
队列q
|
第四次3出队2入队
Dist
| ||||||||
队列q
|
第五次4出队
Dist
| ||||||||
队列q
|
第六次2出队4入队
Dist
| ||||||||
队列q
|
第七次4出队，队列空
Dist
| ||||||||
队列q |
最终输出
2： 1
3： 3
4： 2
相关阅读
此文章转载自：https://blog.csdn.net/heroacool/article/details/51014824迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一
图的有权最短路径 和有向无权图不同的是，有向有权图相邻两个顶点间的边上被赋予一个连接权值。 有权最短路径就是寻找一条路径使
图论的基础知识不再阐述。 最短路径算法主要有二 Dijkstra算法 Floyd算法 Dijkstra算法研究的是从初始点到其他每一结点的最短
本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法1），深度或广度优先搜索