最短路径算法（C语言实现）

最短路径算法（C语言实现）

最短路径算法是图论研究中的一个经典算法问题，其目的是寻找图中两节点之间的最短路径。常用的路径算法有Floyd-Warshall算法、Dijkstra算法、Bellman-Ford算法、Bellman-Ford的队列优化算法（SPFA算法）等。本文将详细介绍这些算法的原理、步骤及应用场景，并通过对比分析帮助读者选择合适的算法。

Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间最短路径的一种算法，可以正确处理有向图的最短路径问题。其原理是动态规划：

假设$D_{i,j,k}$为从$i$到$j$的只以$(1,2,…,k)$集合中的节点为中间节点的最短路径的长度。若最短路径经过点$k$，则$D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$；若最短路径不经过点$k$，则$D_{i,j,k}=D_{i,j,k-1}$。

因此，$D_{i,j,k}=\min(D_{i,k,k-1}+D_{k,j,k-1},D_{i,j,k-1})$。

在实际计算过程中，为了节约空间，可以直接在原来空间上进行迭代计算，这样空间可降至二维。

Floyd-Warshall算法的描述如下：

for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (D[i,k] + D[k,j] < D[i,j]) then
D[i,j] ← D[i,k] + D[k,j];

其中$D_{i,j}$表示由点$i$到点$j$的代价，$D_{i,j}$为$\infty$表示两点之间没有任何连接。

Dijkstra算法

Dijkstra算法思想：假设$G=(V,E)$是一个带权的有向图，首先把图中顶点的集合$V$分成两组，第一组为已求出最短路径的顶点集合$S$，第二组为其余未确定最短路径的顶点集合$U$，按最短路径长度的递增次序依次把第二组的顶点加入$S$中。

然后在加入的过程中，总保持从源点$v$到$S$中各顶点的最短路径长度不大于从源点$v$到$U$中任何顶点的最短路径的长度。

最后每个顶点对应一个距离，$S$中顶点的距离就是从源点$v$到此顶点的最短路径长度，$U$中的顶点的距离就是从源点$v$到此顶点的当前最短路径长度。

Dijkstra算法具体步骤如下：

1. 初始时，$S$只包含源点，即$S＝{v}$，$v$的距离$dist[v]$为0。$U$包含除$v$外的其他顶点，$U$中顶点$u$距离$dist[u]$为边上的权值（若$v$与$u$有边）或$\infty$（若$u$不是$v$的出边邻接点即没有边$<v,u>$）。
2. 从$U$中选取一个距离$v(dist[k])$最小的顶点$k$，把$k$加入$S$中（该选定的距离就是$v$到$k$的最短路径长度）。
3. 以$k$为新选择的中间点，修改$U$中各顶点的距离；若从源点$v$到顶点$u$（$u∈U$）的距离（经过顶点$k$）比原来距离（不经过顶点$k$）短，则修改顶点$u$的距离值，修改后的距离值的顶点$k$的距离加上边上的权值（即如果$dist[k]+w[k,u]<dist[u]$，那么把$dist[u]$更新成更短的距离$dist[k]+w[k,u]$）。
4. 重复步骤2和3直到所有顶点都包含在$S$中（要循环$n-1$次）。

Bellman-Ford算法

Bellman-Ford算法思想：可以在普遍的情况下（存在负权边）解决一些单源点最短路径问题。首先对于给定的带权图$G=(V,E)$，其源点为$s$，加权函数$w$是边集$E$的映射。

对图$G$运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在一个从源点$s$可达的负权回路。若不存在这样的回路，算法将给出从源点$s$到图$G$的任意顶点$v$的最短路径$d[v]$。

Bellman-Ford算法具体步骤如下：

• 初始化：除去源点以外，将所有顶点的最短距离估计值$d[v]←+∞$，$d[s]←0$。
• 迭代求解：反复对边集$E$中的每条边进行松弛操作，使得顶点集合$V$中的每个顶点$v$的最短距离估计值逐步逼近它的最短距离。
• 检验负权回路：在判断边集$E$中的每一条边的两个端点是否收敛时，如果存在未收敛的顶点，则算法返回false，表示问题无解；否则，算法返回true，并且从源点$s$可达的顶点$v$的最短距离保存在$d[v]$中。

对于图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含$|V|-1$条边。从源点$s$可达的所有顶点如果存在最短路径，则这些最短路径构成一个以$s$为根的最短路径树。

Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离$s$的层次，逐层生成这棵最短路径树的过程：

• 在对每条边进行1遍松弛的时候，生成了从$s$出发、层次至多为1的那些树枝。也就是说，找到了与$s$至多有1条边相连的那些顶点的最短路径；
• 对每条边进行第2遍松弛的时候，生成了第2层的树枝，就是说找到了经过2条边相连的那些顶点的最短路径。

因为最短路径最多只包含$|V|-1$条边，所以只需要循环$|V|-1$次。每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。

如果没有负权回路，那么最短路径树的高度最多只能是$|V|-1$，所以最多经过$|V|-1$遍松弛操作后，所有从$s$可达的顶点必将求出最短距离。如果$d[v]$仍保持$+∞$，则表明从$s$到$v$不可达。如果有负权回路，那么第$|V|-1$遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

Bellman-Ford的队列优化算法

由于Bellman-Ford算法经常会在未达到$V-1$次时就出解，$V-1$其实是最大值。所以可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

具体做法是用一个队列保存待松弛的点，然后对每个出队的点依次遍历每个与它有边相邻的点，如果该点可以松弛并且队列中没有该点则将它加入队列中，如此迭代直到队列为空。

与Bellman-ford算法类似，Bellman-Ford的队列优化（SPFA算法）采用一系列的松弛操作以得到从某一个节点出发到达图中其他所有节点的最短路径。不同的是，SPFA算法是通过维护一个队列，使得某一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。

SPFA算法可以存在负数边权的图中，这不同于Dijkstra算法，也不同于Bellman-ford算法，SPFA算法的时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。

在最好情况下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为$O(E)$。另外，也存在一些例子，比如要想使得每一个节点都被入队$(V-1)$次，那么此时算法就退化为Bellman-ford算法，相应地时间复杂度也降为$O(VE)$。

C语言最短路径算法对比分析

SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的堆优化的版本。

Floyd算法虽然总体上时间复杂度较高，但是可以解决负权边问题，并且在均摊到每一点对上，其在所有的算法中还是属于较好的。另外，Floyd算法的编码复杂度较小，这是它的一大优势。所以如果要求的是所有点对间的最短路径较小，或者要求数据范围较小，则Floyd算法比较合适。

Dijkstra算法最大的局限性就是它无法适应有负权边的图。但是它具有良好的可扩展性，扩展后可以适应很多问题。另外用堆优化的Dijkstra算法的时间复杂度可以达到$O(M\log N)$。当所有的边中存在负权边时，需要Bellman-Ford算法。

因此，我们选择最短路径算法时，要根据实际需求和每一种算法的特性，选择合适的算法。

最短路径算法比较

示例：使用Dijkstra算法求解下图中顶点1到各顶点的最短路径

C语言编程代码如下：

#include<stdio.h> 
#include<stdlib.h>
#define MAXNODE 30 /*定义宏*/
#define MAXCOST 1000 /*定义宏*/
int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=5;
void dijkstra(int v0) /*自定义dijkstra()函数，用来求最小生成树*/
{
 int s[MAXNODE];
 int mindis,dis,x,y,u;
 for(x=1;x<=n;x++)
 {
 dist[x]=cost[v0][x];
 s[x]=0;
 }
 s[v0]=1;
 for(x=1;x<=n;x++)
 {
 mindis = MAXCOST;
 for(y=1;y<=n;y++)
 if(s[y]==0&&dist[y]<mindis)
 {
 u=y;
 mindis = dist[y];
 }
 s[u]=1;
 for(y=1;y<=n;y++)
 if(s[y]==0)
 {
 dis = dist[u]+cost[u][y];
 dist[y] = (dist[y]<dis)?dist[y]:dis;
 }
 }
} 
void display_path(int v0) /*自定义display_path()函数，用来输出到各顶点的最短路径*/
{
 int x;
 printf("\n顶点%d到各顶点的最短路径长度如下：\n",v0);
 for(x=1;x<=n;x++)
 {
 printf(" (v%d->v%d):",v0,x);
 if(dist[x]==MAXCOST)
 printf("无路径\n");
 else
 printf("%d\n",dist[x]);
 }
}
int main()
{
 int i,j,v0=1;
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 cost[i][j]=MAXCOST;
 for(i=1;i<=n;i++)
 cost[i][j]=0;
 cost[1][2]=10;
 cost[1][5]=100;
 cost[1][4]=40;
 cost[2][3]=50;
 cost[4][3]=20;
 cost[3][5]=10;
 cost[4][5]=60;
 dijkstra(v0); /*调用dijkstra()函数*/
 display_path(v0); /*调用display_path()函数*/
 return 0;
}

运行结果：

顶点1到各顶点的最短路径长度如下：
(v1->v1):无路径
(v1->v2):10
(v1->v3):60
(v1->v4):40
(v1->v5):70

本例中使用了Dijkstra算法的思想，设置并逐步扩充一个集合$S$，存放已求出的最短路径的顶点，则尚未确定最短路径的顶点集合是$V-S$，其中$V$为网中所有顶点集合。按照最短路径长度递增的顺序逐个将$V-S$中的顶点加到$S$中，直到$S$中包含全部顶点，而$V-S$为空。