数据结构与算法分析（五）——最短路径算法

首页 > 代码库 > 数据结构与算法分析（五）——最短路径算法

数据结构与算法分析（五）——最短路径算法

2024-07-31 13:46:55 225人阅读

0）引论

正如名字所言，最短路径算法就是为了找到一个图中，某一个点到其他点的最短路径或者是距离。

最短路径算法一般分为四种情况：

a）无权重的最短路径

b）有权重的最短路径

c）边的权重为负的图

d）无圈的图

ps：上面的情况针对的都是有向图。

1）无权重的最短路径

下图是一个例子：假设我们取点v3作为初始点，计算点v3到图中所有点的路径以及距离（包括点v3）。

a） v3到v3的路径长为0。

b）沿着v3的邻接点查找，找到v1，那么v3到v1的路径长为1；找到v6，那么v3到v6的路径长为1。

c） v3的邻接点已经找完了，接下来找v1，v6的邻接点。

d） v1的邻接点为v2，v4，它们对应的路经长为2；v6无邻接点，v6部分结束。

e） v2的邻接点为v4，v5，而v4已经查找过了，舍弃；v2到v5的路径长为3；v4的邻接点为v5，v7，而v5已经查找过了，舍弃；v4到v7的路径长为3。

f）至此，结束。

对于这一步骤，可以用一个表格来表示，以便于编程理解：

表中有3个表示状态的变量：

a） dv表示点s到图中每个点的距离，结合上面的例子，s=v3.

b） pv表示图中点的路径前继点。

c） Known表示点是否被处理，处理了，则标记为1 。

伪代码：

 1 void Unweighted(Table T)   2 {   3     int CurrDist;   4     Vertex V,W;   5     for(CurrDist=0;CurrDist<NumVertex;CurrDist++)   6     {   7         for each vertex V   8             if(!T[V].Known&&T[V].Dist==CurrDist)   9             {  10                 T[V].Known = True;  11                 for each W adjacent to V  12                     if(T[W].Dist == Infinity)  13                     {  14                         T[W].Dist = CurrDist+1;  15                         T[W].Path = V;  16                     }  17             }  18     }  19 }

View Code

通拓扑排序一样，对于上面的程序也是存在改进的地方的（第07行），我们没有必要去对each vertex V做一下这么多的步骤，只需要对相邻接的点做就好了。因此用一个队列来使每一个处理的点入队，然后处理其邻接的点。

 1 void Unweighted(Table T)   2 {   3     Queue Q;   4     Vertex V,W;   5    6     Q = CreateQueue(NumVertex);   7     MakeEmpty(Q);   8     Enqueue(S,Q);//S is the start Vertex   9   10     while(!IsEmpty(Q))  11     {  12         V = Dequeue(Q);  13         T[V].Known=True;  14         for each W adjacent to V  15             if(T[W].Dist == Infinity)  16             {  17                 T[W].Dist = T[V].Dist+1;  18                 T[W].Path = V;  19                 Enqueue(W,Q);  20             }  21     }  22     Free(Q);  23 }

View Code

2）有权重的最短路径

有权重的最短路径算法，称之为Dijkstra‘s algorithm。相对于无权重的最短路径算法，有权重的最短路径算法会显得难一点，这是因为权重的引入会使某些路径的加权重长度发生颠倒。

Dijkstra‘s algorithm是一种greedy algorithm。贪婪算法就是在算法的每一个阶段都取最大值。一般情况下，贪婪算法能取得较好的效果。但是贪婪算法是有其缺陷的，也就是说能达到局部最优，而未必能达到全局最优，举个例子，假设要兑换15分的硬币，而硬币有12分的，10分的，5分的，1分的，那么根据贪婪算法，最终的兑换结果为1个12分的，3个一分的；而最优结果应该是一个10分的，一个5分的。（这里我们定义最优为硬币个数最少）。

Dijkstra‘s algorithm的步骤是：

对于每一个阶段，Dijkstra‘s algorithm会在所有未处理的点中选取一个最小距离的点v，然后把给定点s到v的路径定义为最小路径。

下面是一个例子：

对应的表的形式表示：

下面是具体的实现说明：

a）最初的点s=v1；计算s到图中所有点的最短路径。

b）找到v1邻接的点v2，v4，分别标出s到v2，v4的路径长，同时对v1标注T[v1].Known=1。

c）由于v4路径长较小，因此选择v4，找到v4邻接的点v3，v5，v6，v7，标注出他们的路径长；同时对v1标注T[v4].Known=1。

d）现有的所有未处理路径中v2最短，因此处理v2，找到v2邻接的点v4，v5； v2到v4，v5的路径长远大于v4，v5已有的路径长，因此不更新。同时T[v2].Known=1。

e）现有的所有未处理路径中v3，v5最短，处理v3，邻接点为v1，v6，路径分别为7,8；对于v3到v6的距离，因为8<9，因此需要更新；对于v3到v1的距离不需要更新。同时T[v3].Known=1。

f）对于v5，邻接点为v7，v5到v7的路径长为 3+6>5，因此不更新；同时T[v5].Known=1。

g）现在处理v7，v7的邻接点为v6，v7到v6的路径长为5+1<8，因此需要更新；同时T[v7].Known=1。

h）现在处理v6，v6没有邻接点了，因此可以结束了。同时T[v6].Known=1。

伪代码实现：

 1 typedef int Vertex;   2 typedef int DistType;   3    4 struct TableEntry   5 {   6     List Header;   7     int Known;   8     DistType Dist;   9     Vertex Path;  10 }  11   12 #define NotAVertex (-1)  13 typedef struct TableEntry Table[NumVertex];  14   15 void InitTable(Vertex Start,Graph G,Table T)  16 {  17     int i;  18     ReadGraph(G,T);  19     for(i=0;i<NumVertex;i++)  20     {  21         T[i].Known = 0;  22         T[i].Dist = Infinity;  23         T[i].Path = NotAVertex;  24     }  25     T[Start].Dist = 0;  26 }  27   28 void Dijkstra(Table T)  29 {  30     Vertex V,W;  31     for(;;)  32     {  33         V = FindSmallestUnknownDistanceVertex();  34         if(V==NotAVertex)  35             break;  36         T[V].Known = Ture;  37         for each W adjacent to V  38             if(!T[V].Known)  39                 if(T[V].Dist+Cvw<T[W].Dist)  40                 {  41                     Decrease(T[W].Dist to T[V].Dist+Cvw);  42                     T[W].Path = V;  43                 }  44     }  45 }