★ 第六十四讲 最短路径|【迪杰斯特拉算法】★

不二如是

                               
登录/注册后可看大图

  

索引帖

  

用一节课的时间，提高生活幸福感

------小甲鱼

欢乐与傻笑并存

智慧与邪恶同在

笔记内涵------

---

最短路径

在网图和非网图中，最短路径的含义是不同的。

网图是：

        两顶点经过的边上权值之和最少的路径。

非网图是：

        两顶点之间经过的边数最少的路径。

我们把路径起始的第一个顶点称为源点，最后一个顶点称为终点。

关于最短路径的算法，我们会介绍两种：

        迪杰斯特拉算法（Dijkstra）

        弗洛伊德算法（Floyd），下一讲介绍。

---

小游戏

求V0到V8的最短路径（注意权值哈）：

答案：

---

迪杰斯特拉算法原理

简介：

        迪杰斯特拉算法（英语：Dijkstra's algorithm）是由荷兰计算机科学家[b]艾兹赫尔·戴克斯特拉[/b]提出。

        迪杰斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到一个最短路径树。

        该算法常用于路由算法或者作为其他图算法的一个子模块。

        举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

好了，我想你大概明白了，这个迪杰斯特拉算法是如何工作的。

它并不是一下子就求出了V0到V8的最短路径，而是一步步求出它们之间顶点的最短路径。

过程中都是：

        基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

如果还不大明白，没关系，小甲鱼带着大家一起来解读代码。

把自己模拟成计算机，模拟代码的运行，再次去理解它的思想。

---

代码解读时刻

代码：

#define MAXVEX        9
#define        INFINITY        65535

typedef        int        Patharc[MAXVEX];                        // 用于存储最短路径下标的数组
typedef int        ShortPathTable[MAXVEX];                // 用于存储到各点最短路径的权值和

void ShortestPath_Dijkstar(MGraph G, int V0, Patharc *P, ShortPathTable *D)
{
        int v, w, k, min;
        int final[MAXVEX];                // final[w] = 1 表示已经求得顶点V0到Vw的最短路径
        
        // 初始化数据
        for( v=0; v < G.numVertexes; v++ )
        {
                final[v] = 0;                                // 全部顶点初始化为未找到最短路径
                (*D)[V] = G.arc[V0][v];                // 将与V0点有连线的顶点加上权值
                (*P)[V] = 0;                                // 初始化路径数组P为0
        }
        (*D)[V0] = 0;                // V0至V0的路径为0
        final[V0] = 1;                // V0至V0不需要求路径
        
        // 开始主循环，每次求得V0到某个V顶点的最短路径
        for( v=1; v < G.numVertexes; v++ )
        {
                min = INFINITY;
                for( w=0; w < G.numVertexes; w++ )
                {
                        if( !final[w] && (*D)[w]<min )
                        {
                                k = w;
                                min = (*D)[w];
                        }
                }
                final[k] = 1;        // 将目前找到的最近的顶点置1
                
                // 修正当前最短路径及距离
                for( w=0; w < G.numVextexes; w++ )
                {
                        // 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
                        if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )
                        {
                                (*D)[w] = min + G.arc[k][w];        // 修改当前路径长度
                                (*p)[w] = k;                                        // 存放前驱顶点
                        }
                }
        }
}

结果：

D:     0 1 4 7 5 8 10 12 16
P:     0 0 1 4 2 4 3 6 7
final: 1 1 1 1 1 1 1 1 1

这位鱼油，如果喜欢本系列笔记，请订阅 专辑☞（传送门）（不喜欢更要订阅 ）

chhch

有没有关于邻接表的最短路径算法呢?

zxh.

为什么我觉得 min = (*D)[w];这个代码是错的，当我k=1的时候会对  (*D)[3]赋值为8，当k＞＝3的时候，就没办法把他的值了改为7了