最短路径算法汇总

mscdj 2018-01-11

展开全文

1.Floyd

2.Dijkstra

3.SPFA（队列优化Bellman算法）

4.Best-First-Search——A算法

5.启发式A*

6.启发式的A*的平局打破

7.目前自学存在的急需解决的问题

8.最短路径算法的优劣比较

9.各个算法的路径记录的策略

1.Floyd（全局最短路径算法）

1）数据结构的选择：

Floyed算法是需要不断的通过第三方节点来松弛目标两个节点之间的距离，通过遍历图中所有的顶点，从而实现全局最短路径的求解

所以这里，我们的两点之间的边权值是要不断的改变的，所以我们果断采用邻接矩阵来进行图的存储，这样会更加利于操作

2）算法的核心：

我们通过求解最优子路径来求得全局最优路径，在这里，两个点之间的最优路径要么就是两点之间直接的连边，要么就是通过其他若干

的节点来进行松弛，所以，这里面我们一各个点为基准，构建三个循环，最外面的循环遍历所有的第三方节点，里面的循环控制两个目标

节点，在这里，可能有的人会问了，这样的话，只是以一个节点作为中间节点来考虑的，但是实际上，有可能最短路径包含不止一个中间节点

没错，在这里，我们要这么考虑，每次一个中间节点考虑完之后，邻接矩阵中的所有的边的权重都是考虑了这个已经考虑过得第三方节点

优化后的结果，所以我们下次再用别的第三方节点的时候就必然会将之前的所有的考虑过得第三方节点都纳入考虑过的优化范围之内，所以

最后的结果就是，我们任意两点之间的最短路径都是考虑了所有的第三方节点来进行优化的

个人感觉一点：Floyd的本质很可能就是动态规划

3) 核心代码段：

[html] view plain copy

print?

for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; //考虑第三方节点k的优化
}
}
}

4）Floyed可以解决负权边，在下面我会提出问题，无向图的负权边会重复考虑吗？

Floyed不可以解决负权回路，因为负权回路不存在最短路径

2.Dijkstra（单源最短路径算法）

1）数据结构的选择：

Dijstra的核心是不断的维护一个dis数组，最后得到的dis数组中的左右的权重就是源点到图中所有的节点的最短路径的长度，所以在这里

数据结构我们是不必过分的强求的，邻接矩阵，邻接表，链式前向星，边集数组都是可以的，这里我们用数组模拟链表来进行数据结构的讲解

其他的数据结构在理解了核心的之后都是轻而易举

2）算法的核心：

1》算法大致流程：

a.录入图的信息完成初始化

b.找到在dis数组中权重最小的节点p（目前距离源节点最近的节点）

c.利用p的所有的出边优化源节点到p出边的临近节点的边权值

d.图中除了源节点以外的n-1个点都已经优化过，继续e，否则返回b

e.输出dis数组的权重

2》算法讲解：

Dijstra算法其实很好理解，我们每次利用距离原点最近的节点作为第三方节点来优化源节点和第三方节点的出边临近节点，当所有的

节点全部考虑完了以后，我们得到的必然就是单源节点到其余节点的最短路径

先对朴素的Dijstra来说，我们需要用book数组记录那些节点我们已经访问过，在遍历求解距离单源点最近的节点的时候我们可以不访问

那些考虑过的节点

2.1》朴素的Dijstra算法的示例代码：

[cpp] view plain copy

print?

#include"iostream"
#include"cstdio"
#include"cstdlib"
#define inf 99999999
#define Nedge 5000
#define Npoint 1000
using namespace std;
int u[Nedge];
int v[Nedge];
int w[Nedge];
int first[Npoint];
int nextk[Nedge];
//上面是链式前向星的数据结构
int book[Npoint];
int npoint,nedge;
int dis[Npoint];
int main()
{
cin>>npoint>>nedge;
memset(book,0,sizeof(book));
memset(first,-1,sizeof(first));
memset(nextk,0,sizeof(nextk));
for(int i=1;i<=nedge;i++)
{
int a,b,c;
cin>>u[i]>>v[i]>>w[i];
nextk[i]=first[u[i]];
first[u[i]]=i;
}
book[1]=1;
int k=first[1]; //这里讲 1 当做源节点，下面的代码是对dis进行初始化
for(int i=1;i<=npoint;i++) dis[i]=inf;
while(k!=-1)
{
dis[v[k]]=w[k];
k=nextk[k];
}
dis[1]=0; //自己到自己的距离肯定是0
for(int i=1;i<=npoint-1;i++)
{
int minedge=inf;
int minpoint;
for(int i=1;i<=npoint;i++) //找到最近的节点
{
if(book[i]==0&&dis[i]<minedge)
{
minpoint=i;
minedge=dis[i];
}
}
book[minpoint]=1;
k=first[minpoint];
while(k!=-1) //松弛出边
{
if(book[v[k]]==0&&dis[v[k]]>dis[minpoint]+w[k]) dis[v[k]]=dis[minpoint]+w[k];
k=nextk[k];
}
}
for(int i=1;i<=npoint;i++) cout<<dis[i]<<' ';
return 0;
}

在这里我们要注意因为每次选最近的点都要进行遍历操作，但是我们可以优化一下，对，我们可以用堆，根据dis中的权重为判断依据，我们来构建最小堆，可以大大提高Dijstra的速度

2.2》堆优化Dijstra算法代码示例：

[cpp] view plain copy

print?

#include"iostream"
#include"cstdio"
#include"cstdlib"
#define inf 99999999
#define NP 1000
#define NE 2000
using namespace std;
int u[NE];
int v[NE];
int w[NE];
int first[NP];
int nextk[NE];
int dis[NP];
int heap[NP];
int pos[NP]; //pos记录i号节点在堆中的位置，在变松弛之后方便向上调整
int heapnumber=0;
int n,m;
void swap(int x,int y)
{
int t=heap[x];
heap[x]=heap[y];
heap[y]=t;
t=pos[heap[x]]; //同步更新
pos[heap[x]]=pos[heap[y]];
pos[heap[y]]=t;
}
void siftdown(int i)
{
int t,flag=0;
while(i*2<=heapnumber&&flag==0)
{
if(dis[heap[i]]>dis[heap[i*2]]) t=i*2;
else t=i;
if(i*2+1<=heapnumber&&dis[heap[i*2+1]]<dis[heap[t]]) t=i*2+1;
if(t!=i)
{
swap(i,t);
i=t;
}
else flag=1;
}
}
void siftup(int i)
{
int t,flag=0;
while(i!=1&&flag==0)
{
if(dis[heap[i]]<dis[heap[i/2]])
{
swap(i,i/2);
i=i/2;
}
else flag=1;
}
}
int pop()
{
int t=heap[1];
swap(1,heapnumber);
heapnumber--;
siftdown(1);
return t;
}
int main()
{
cin>>n>>m;
heapnumber=n;
for(int i=1;i<=n;i++)
{
first[i]=-1;
nextk[i]=0;
heap[i]=pos[i]=i;
dis[i]=inf;
}
dis[1]=0; //以 1 为源点
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i]>>w[i];
nextk[i]=first[u[i]];
first[u[i]]=i;
}
int k=first[1];
while(k!=-1) //初始化dis数组
{
dis[v[k]]=w[k];
k=nextk[k];
}
for(int i=n/2;i>=1;i--) siftdown(i); //初始化堆
pop();
for(int i=1;i<=n-1;i++)
{
int minpoint=pop();
k=first[minpoint];
while(k!=-1)
{
if(book[v[k]]==0&&dis[v[k]]>dis[minpoint]+w[k])
{
dis[v[k]]=dis[minpoint]+w[k];
siftup(pos[v[k]]);
}
k=nextk[k];
}
}
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}

3）Dijkstra分析：援引大神的解释为什么Dijstra不能解决负权边——贪心的前提错误

还有我们的Dijstra算法的过程中注意，我们必须要对访问过的点进行标记，之后松弛的时候我们是不松弛被访问的点的

点击打开链接

我们首先来分析下含负权边的无向图：

1.先看图
我们求A点到C点的最短距离，很明显答案为1.
2.我们用dij来跑下，看过程：

先把A点标记哈，不需要访问本身
首先找到距A最近的且直接相连的点（也就是两点间没有中转点）C，把C标记哈
找出C点的出点A,，B，A被标记了不管，此时A到B的距离为3，大于A到C的距离加上C到B的距离0，所以更新A到B的距离为0
更新后A到C的距离仍然为2，A到B的距离为0，A，C都被标记，只有B未被标记，进行下一步
找到距A最近的且未被标记的点B，标记B
找出B的出点A，C，然而A，C两点都被标记，不能松弛
好，程序结束，结果为A到C的距离为2而不是1，说明普通dij并不能处理带负权边的无向图

3.看完了dij过程可能仍有人不是很明白为什么，没关系，待会儿会详细解释，现在我们看下带负权边的有向图：

4.如图，我们还是求A到C的最短距离，很明显，答案还是15.我们还是用dij来跑下：

先把A点标记哈，不需要访问本身
首先找到距A最近的且直接相连的点（也就是两点间没有中转点）C，把C标记哈
找出C点的出点，哦豁，莫得，不方，莫得就不管，走下一步
找到距A最近的且未被标记的点B，标记B
找出B的出点C，好，松弛，等等！！！松弛个锤子，C是标记了的，按照dij远的点是不能松弛近的点的，所以不能松弛。
好，程序结束，结果为A到C的距离为2，跟答案不同。说明也不能用dij来处理带负权边的有向图。

PS（有的人在倒数第二步没有判断点是否标记，导致求出来的结果是1，然而这时错误的，下面我将说明）
6.我们来看看原因：
我们先来看看dij的由来，dij求最短路的算法是由贪心得来的，也就是说长路径的松弛正确的前提是用来松弛它的短路径是最短的，也就是说在之后是不会变的，这在非负权值的情况下是对的，然而遇到负权值便错了，因为当加入了负权值边后便可能使之前的短边变得更短，就如图中一样，我们先访问了C点，则AC的距离在之后的距离应该是不变的，这在都是非负权值时是正确的，因为每条边都是非负的，当通过其他点来中转时，所经过的路径和必然不小于AC的距离，然而加入了负权边后，使得AC的距离变得比初始更小，这便使得前提错误，前提都错了，dij算法便不成立，结果便错误，这也是为什么有那么多人糊涂的原因，也是我专门举这个例子的原因

3.SPFA (Bellman队列优化，单源最短路径)

1）数据结构的选择：

和Dijstra的操作大致相似，我们也是要维护dis数组，换言之，dis数组的结果也就是最后的单源最短路径的结果

所以，这里我们和Dijstra算法的数据结构是基本一样的，我们举例也是通过模拟链表的方式来进行讲解

2）算法讲解:

2.1》Bellman算法步骤：

首先，我们要先弄懂Bellman算法的原理，Bellman算法算法和Dijstra还是有区别的，Dijstra算法是枚举点，但是Bellman算法是枚举边，我们换个角度，从原点到所求的点之间的路径优化的方式可以看做是第三方节点加上第三方节点与目标节点之间的一条边，所以我们通过枚举边来优化两点之间的路径，但是要优化几轮才够呢我们可以这么来看，每次成功优化的时候，两点之间的路径是会被扩展成另外一组路径的，这组路径的边的个数比原先的路径的个数总是多1，所以，我们发现假如：最坏的情况就是源节点n到目标结点p之间的路径需要通过图中的所有的点来进行辅助才能优化，那么我们需要进行多少轮，才能成功将n与p之间的路径优化到最短呢，（假设有k个节点k个节点全部连接至少要k-1条边）显然，答案是k-1，因为刚开始的时候我们一条边都没有松弛，所以，可以推理出，我们总共需要k-1轮就可以成功优化出单源最短路径

2.2》SPFA算法：

在了解了Bellman算法之后，我们开始着手SPFA算法，SPFA算法实际上是对Bellman的一种优化，我们发现实际上，Bellman算法其实有的时候没必要进行n-1轮就可以结束，因为n-1轮是最坏的情况，所以我们什么时候开始判断可以结束了呢

这时候我们发现，假设有一个点刚刚被优化了，我们可以很明显的发现，针对这条边，也就只有这条边的出边上的终点才可以继续被优化，这就给了我们启示，其实我们可以再维护一个队列，一个点如果被优化过了，那么就进队列，（当然我们这么做还需要开一个book记录数组记录在队列中的节点），我们只需要对队列中的点的出边进行松弛就可以了，当队列空的时候说明松弛结束，最短路径已经求出来了

3）代码示例：SPFA

[cpp] view plain copy

print?

#include"iostream"
#include"cstdio"
#include"cstdlib"
#define inf 99999999
#define NP 1000
#define NE 2000
using namespace std;
int queue[NP*2];
int head,tail;
int dis[NP];
int book[NP];
int n,m;
int u[NE];
int v[NE];
int w[NE];
int first[NP];
int nextk[NE];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
dis[i]=inf;
first[i]=-1;
nextk[i]=0;
book[i]=0;
}
memset(queue,0,sizeof(queue));
head=tail=1;
dis[1]=0; //假设 1 为源点
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i]>>w[i];
nextk[i]=first[u[i]];
first[u[i]]=i;
}
queue[1]=1;
tail++;
book[1]=1; //小心这里dis一定不可以先初始化，因为一旦初始化将源节点的出边进行添加的话，源节点的出边的弧头书不会入队列的，算法就 //出现问题了
while(head!=tail)
{
int k=first[queue[head]];
while(k!=-1)
{
if(dis[v[k]]>dis[u[k]]+w[k])
{
dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0)
{
book[v[k]]=1;
queue[tail]=v[k];
tail++;
}
}
k=nextk[k];
}
book[queue[head]]=0; //这一步是非常有必要的
head++;
}
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}

4）总结:

在最后，我强调一点，SPFA是可以正确的求解出负权边的

PS:2016-11-21

发现思维漏洞：

对于SPFA算法，如果我们每一个队列中的顶点松弛出边之后并没有将顶点的访问标记去掉的话，会导致程序出现错误

错误的原因很简单：

[cpp] view plain copy

print?

1
3
4 5 6

无向或者有向边为

1 2 1

1 3 5

3 4 1

3 5 1

3 6 1

如果我们不将3号顶点取出队列的话，我们会发现，通过2顶点我们可以对3重新松弛，但是3不出顶点的话，我们无法对4,5,6继续松弛，这是有问题的

所以中间注释的那一句book[queue[head]]=0;是非常有必要的

5）SPFA的拓展应用：

我们如果在优化完了以后，重新遍历一边所有的边，如果我们发现仍按存在可以松弛的情况，只能说明一点，存在负权回路

4.Best-First-Search(带启发函数的最短寻路算法 A)

1）简介：

虽然缩写也是BFS，但是不同于BFS，实际上我们也可以将最佳优先搜索称之为A算法，最佳优先搜索算法实际上在图搜索中应用的更为广泛,因为最佳优先算法和A*算法实际上都是在图上寻找出一条最短路径的，当然我们这里书他是启发式的，是因为和盲目搜索不同

BFS‘（最佳优先算法）通过启发估价函数来指向目标，所以可以比在图搜索中的Dijstra的四周盲目搜索更有目的性，当然也就更快

2）实现：

在下实在是才疏学浅，瞻仰大神们的博客之后才率为了解了一点原理，这里的原理就只有启发估价函数F(n)了，

F（n）=h(n) //h（n）是当前位置到终点位置的估价，目的是，尽量避免盲目搜索，让搜索具有优先性，

3）数据结构的选择：

我们既然是有优先性的选择的话，那么我们就需要一个优先队列来实现维护一个Open表，然后我们再用一个Close表来保存已经访问过的位置

4）算法描述：

最佳优先搜索的过程可以被描述为：

a.将根节点放入优先队列open中。

b.从优先队列中取出优先级最高的节点X。

c.根据节点X生成子节点Y:

c.1. X的子节点Y不在open队列或者closed中，由估价函数计算出估价值，放入open队列中。

c.2. X的子节点Y在open队列中，且估价值优于open队列中的子节点Y，将open队列中的子节点Y的估价值替换成新的估价值并按优先值排序。

c.3. X的子节点Y在closed集中，且估价值优于closed集中的子节点Y，将closed集中的子节点Y移除，并将子节点Y加入open优先队列。 //c.3的目的是：把优化后的位置的参数保留下来，让其对后续扩展节点都进行优化

d.将节点X放入closed集中。

e.重复过程2,3,4直到目标节点找到，或者open为空，程序结束。

5）代码示例：

简易的题目描述，找到从起点到终点的最短路径，（在二维地图上）0表示空地，1表示障碍物，并输出路径（本问题中采用的启发式函数应用欧几里得距离——连线距离）

[cpp] view plain copy

print?

#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cmath"
#define N 1000
using namespace std;
typedef struct node
{
int c;
int x,y;
double prev; //优先顺序
int px,py; //记录前驱，输出路径的时候需要
}point;
int book[100][100]; //记录是否在close数组里面
point map[100][100];
point pre[N]; //堆
int numpre=0;
point close[N];
int numclo=0;
int nextk[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; //四个方向的扩展
int n,m;
int sx,sy;
int ex,ey;
void swap(int x,int y)
{
point t=pre[x];
pre[x]=pre[y];
pre[y]=t;
}
point count(int x,int y)
{
point w;
w.x=x;w.y=y;
w.prev=sqrt(pow(w.x-ex,2)+pow(w.y-ey,2));
return w;
}
void siftup(int i)
{
int t,flag=0;
while(i!=1&&flag==0)
{
if(pre[i].prev<pre[i/2].prev)
{
swap(i,i/2);
i=i/2;
}
else flag=1;
}
}
void siftdown(int i)
{
int t,flag=0;
while(i*2<=numpre&&flag==0)
{
if(pre[i].prev>pre[i*2].prev) t=i*2;
else t=i;
if(i*2+1<=numpre&&pre[i*2+1].prev<pre[t].prev) t=i*2+1;
if(t!=i)
{
swap(i,t);
i=t;
}
else flag=1;
}
}
point pop()
{
point k=pre[1];
pre[1]=pre[numpre];
siftdown(1);
numpre--;
close[++numclo]=k;
book[k.x][k.y]=1;
return k;
}
void push(int x,int y,int a,int b)
{
pre[++numpre].x=x;pre[numpre].y=y;
pre[numpre].px=a;pre[numpre].py=b;
pre[numpre].prev=count(x,y).prev;
siftup(numpre);
}
bool judgeopen(int x,int y)
{
for(int i=1;i<=numpre;i++)
{
if(pre[i].x==x&&pre[i].y==y) //因为我把g（n）耗散函数设为零了，这样方便一点，这一向我们就可以不用进行处理了
return 1;
}
return 0;
}
bool judgeclose(int x,int y,int a,int b)
{
for(int i=1;i<=numclo;i++)
{
if(x==sx&&y==sy) return 1;
if(close[i].x==x&&close[i].y==y&&count(x,y).prev<close[i].prev)
{
pre[++numpre]=close[i];
pre[numpre].px=a,pre[numpre].py=b;
pre[numpre].prev=count(x,y).prev;
return 1;
}
}
return 0;
}
int main()
{
memset(book,0,sizeof(book));
cin>>n>>m;
memset(map,0,sizeof(map));
memset(pre,0,sizeof(pre));
memset(close,0,sizeof(close));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>map[i][j].c;
}
}
cin>>sx>>sy>>ex>>ey;
map[sx][sy]=count(sx,sy);map[sx][sy].px=map[sx][sy].py=0;
pre[1]=count(sx,sy);pre[1].px=pre[1].py=0;
numpre++;
while(numpre!=0)
{
point w=pop();
for(int i=0;i<4;i++)
{
int dx=w.x+nextk[i][0];
int dy=w.y+nextk[i][1];
if(book[dx][dy]==0)
{
map[dx][dy].x=dx;map[dx][dy].y=dy;
map[dx][dy].px=w.x;
map[dx][dy].py=w.y;
}
if(dx==ex&&dy==ey)
{
numpre=0;
break;
}
if(map[dx][dy].c==1||dx<1||dx>n||dy<1||dy>m||book[dx][dy]==1) continue;
if(judgeopen(dx,dy));
else if(judgeclose(dx,dy,w.x,w.y));
else push(dx,dy,w.x,w.y);
}
}
point stack[N];
memset(stack,0,sizeof(stack));
int numberofstack=0;
stack[1]=map[ex][ey];
numberofstack=1;
while(!(stack[numberofstack].px==0&&stack[numberofstack].py==0))
{
stack[numberofstack+1]=map[stack[numberofstack].px][stack[numberofstack].py];
numberofstack++;
}
for(int i=numberofstack;i>=1;i--) cout<<'('<<stack[i].x<<','<<stack[i].y<<')'<<endl;
return 0;
}