上篇博客我们详细的介绍了两种经典的最小生成树的算法,本篇博客我们就来详细的讲一下最短路径的经典算法----迪杰斯特拉算法。首先我们先聊一下什么是最短路径,这个还是比较好理解的。比如我要从北京到济南,而从北京到济南有好多条道路,那么最短的那一条就是北京到济南的最短路径,也是我们今天要求的最短路径。
因为最短路径是基于有向图来计算的,所以我们还是使用上几篇关于图的博客中使用的示例。不过我们今天博客中用到的图是有向图,所以我们要讲上篇博客的无向图进行改造,改成有向图,然后在有向图的基础上给出最小生成树的解决方案。本篇博客我们的思路与之前数据结构相关博客的风格保持一致,首先我们先给出迪杰斯特拉算法的原理以及详细的示意图,然后根据这些示意图给出具体的实现方案。
一、迪杰斯特拉算法原理解析
在博客的第一部分,我们不谈任何与代码相关的内容,只谈迪杰斯特拉算法的原理以及生成最短路径的具体步骤。下方我们会给出迪杰斯特拉算法的计算最短路径的每一步,并给出每一步具体的说明。废话少说,进入本部分的主题。
1、有向带权图
本篇博客依然采取我们之前用的图的结构。不过我们本篇博客使用的是有向图。下方这张图就是是我们之前使用的无向图转换过来的,只是给之前的图的边添加的具体的方向,其他的并为改动。由无向图转换后的有向图如下所示,我们将在下方的图的基础上计算出从A到D的最短路径。
2.迪杰斯特拉算法的具体步骤
下图就是求上图中A->D的最短路径时使用迪杰斯特拉算法的具体步骤。迪杰斯特拉算法主要核心思想是由起始结点开始,慢慢的由尾结点扩散。直到扩展到尾结点位置。下方我们将根据每个步骤给出具体的介绍:
3、迪杰斯特拉算法的数据表示
上面是我们使用图形的方式给出了迪杰斯特拉算法的具体步骤,接下来我们会把上面的步骤转换成数据的表示方式,以便于我们使用程序进行计算。下方就是上面这些示意图的的完整的数据表示。下方矩阵中的数据标志着起始节点到该节点的距离。由上到下,以此增加距离的大小,而最上面一排的红色字母,标示着该结点的前驱。下方我们在给出每一个行数据的详细介绍。
其实上图就是我们之前原理图的数据表示,接下来我们就要根据这些原理图和数据图来给出我们的代码实现,当然我们还是使用Swift语言来实现。
二、迪杰斯特拉算法的具体实现
1.上述原理总结
上面说这么多,简单的总结一下,上面整个过程无非就是下面这两步的循环,而循环结束的条件就是最短路径延伸到结束路径即可,也就是我们本例中的D点。
经过这么一分析,在给出具体的代码实现就显得简单多了,我们的程序整体上来说就是一个循环,里边包含着上面这两步。
2.具体代码实现
分析完原理后,接下来我们就要开始实现我们的代码了。下方就是我们整个代码的具体实现。当然,我们的图结构是以邻接链表的形式存储的有向联通图。具体代码实现如下所示:
(1)路径结构的存储
我们先创建一个DistanceInfo类,该类中记录了一些距离信息。previousNoteIndex字段存储的是当前节点的前驱节点的索引,默认为-1。而distance存储的就是起始结点到该节点的距离,默认是最大距离。而isInPath则标记该结点是否位于已生成路径的上,如果是的话就是true, 如果不是就是false,默认是false。
(2)代码的整体结
下方代码块就是我们迪杰斯特拉算法代码实现的整体结构。首先我们会创建一个distanceInfos数组,数组中元素的个数就是图的结点的个数。其中存储的是DistanceInfo的对象,每个数组索引对应的DistanceInfo对象中存储的信息就是起始结点到该结点的距离信息。首先我们对起始结点的DistanceInfo对象进行初始化。
紧接着下方这个循环就是我们上面所说的循环,循环结束的条件就是将最短路径延伸到end结点。循环中主要有两步,第一步是在当前循环的index对应的结点上发展新的路径,第二步就是在这些发展的路径中寻找最短路径,在这个新最短路径的基础上再次发展新的路径。
(3)发展新的路径
接下来我们来看一下countCurrentNoteAllDistance()方法中的代码,也就是发展新的路径的代码。主要就是遍历邻接链表上当前索引所连的链表上的数据,将这些数据所对应的结点添加到我们的路径上。往路径上添加新的结点是要注意一点,比如A->D是100, 之前B->D是80,如果现在的路径要比之前的路径要大就不更新,反之就更新我们距离信息数组中的DistanceInfo对象。具体代码如下所示:
(4)、寻找最小路径
下方代码就是寻找当前已发展的所有路径中最短的那条路径,主要还是对DistanceInfo数组的操作。下方代码,找到最短路径后,并把最短路径的索引进行返回。
上方就是我们迪杰斯特拉算法代码实现的核心代码。
三、测试用例
实现完代码后,我们就要对代码进行测试了。下方就是我们的测试用例,该测试用例中创建的图是有向连通图,并且要求出节点A->D的最短路径。
上述测试用例的输入结果如下:
今天的博客就先到这儿,本篇博客所涉及的Demo也将会在github上进行分享,分享地址如下:
github分享地址:https://github.com/lizelu/DataStruct-Swift/tree/master/ShortestPathDijkstra