迪杰斯特拉算法计算最短路径 - 图文

5.2.2 dijkstra算法

这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。

算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展[2]。

简而言之，这种算法就是逐点计算从起点到各个驻点的最短路程，进而得出两点之间的最短路径。算法计算过程中，将遍历所有点，因此所得的结果十分准确，与效率相关的分析将在后文给出。 5.2.3 模型的求解

我们利用matlab软件对模型进行了求解。 得出的结果如下：

环游世界共需79天，即可以赢得赌注

经历的的城市编号如下：1、6、7、12、17、22、23、28、31、32、35、37、39、41、47、50、53、1’。

线路如下图所示：

5.3 以纽约和上海为起点的环球旅行 5.3.1 以上海为起点

数据处理与求解的过程与伦敦相仿，因此不再赘述，具体的数据处理等见附录。所得的结果如下：

环球旅行共需75天。

旅行所经城市路线图如下：

5.3.2 以纽约为起点

数据处理也不再赘述，结果如下：

环球旅行所需天数75天，路线图如下：

六、模型优化

Dijkstra 算法是经典的解决最短路径问题的算法，它可以找出指定节点到其他各个节点间的最短路径，其主要思想是首先从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。这一点在上文中有详细的叙述。

由其算法步骤可知，用标记法实现Dijkstra 算法的主要步骤是从未标记的节点中选择一个权值最小的链路作为下一个转接点，而要选择一个权值最小的链路就必须把所有节点都扫描一遍，在大数量节点的情况下，这往往成为制约算法计算效率的关键因素。而本题正是这种情况。因此，我们认为，这一算法是可以进行优化处理的。 6.1 优化思路一

通过分析传统Dijkstra 算法的基本思路，我们认为，原始Dijkstra算法搜索的核心是从临时标记的点中选择一个权值最小的弧段，即每次在V—s查找距离源点最近的节点。这个过程可以近似为以源点为圆心的一系列同心圆，搜索过程没有考虑终点所在的方向和位置，在从源点出发的搜索过程中，其他节点与终点被搜索到的概率是相同的。为了减小算法中成功搜索的搜索的范围，以尽快达到目标节点，可以对原始Dijkstra算法进行优化。思路是：考虑到交通道路网络的搜索不同于一般数学上的网络搜索，节点位置总是与一定的空间位置相联系，所以从源点到终点的搜索也应具有一定的方向性。如果在运算过程中，首先沿着有效方向进行搜索，那么运算量将会大大降低[3]。

根据分析，我们通过讨论，提出以下两种优化思路。

一、引入一个辅助变量Di，表示每个节点Si到终点的直线距离。对于每个当前所找到的终点Zi，确定下一个终点时Zi+1时，如果Di+1>Di，就将此路径舍弃，这样就减少了大量不必要的计算。为提高准确性，也可将Di+2与Di进行对比，或将Di+2与Di进行对比，依此类推，对比的两个点越“远”，准确性越高，当然，计算量也越大。考虑到距离与时间并不成严格的正比关系，而且实际问题复杂多变，由此计算的路径可能有偏差，因此，此种优化思路只适用于精度要求不高的最短路问题，不保证得出的路径是最短路径。

二、引入一个辅助变量θi，表示每个节点Si与终点连线到水平方向的夹角（逆时针为正），

对于每个当前所找到的终点Zi，确定下一个终点时，只在θi±90o的范围内搜索。同样，采用这种优化思路所得出的最短路也不一定是最短的路径，但计算的复杂度降低了很多。

对于以上两种思路中的直线距离和角度如何得出，是需要进一步研究的问题。

6.2 优化思路二

通过分析传统Dijkstra 算法的运算过程，我们还发现，由于题目中给出的不同路线的交通网络图属于稀疏图，即图中很多地点之间是不能直接到达的，在传统Dijkstra 算法中它们之间路径的权重为∞。因此，在运算的过程中，要进行很多次与∞的比较，这些比较是完全没有必要的。

通过查找资料，我们发现可以用邻接多重表的存储结构解决这一问题。 6.2.1 邻接多重表结构