Dijkstra算法地铁站台出口路径的选择研究(4)
时间:2018-05-08 10:31 来源:毕业论文 作者:毕业论文 点击:次
Floyd-Warshall的原理是动态规划： 设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路径不经过点k，则Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二文。 Floyd-Warshall算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j; 其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。 2.2.2 Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。 当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。 2.2.3 Bellman-Ford 求单源最短路径，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。 Bellman-Ford算法是求解单源最短路径问题的一种算法。 与Dijkstra算法有所不同的是，在Bellman-Ford的算法中，边的权值是可以为负值的，设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负，那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去，而Bellman-Ford算法具有分辨这种负环路的能力。 2.2.4 SPFA[16] 与Bellman-Ford相比，SPFA算法是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。 与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过文护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。 SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。 与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。 SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。 2.2.5 算法分析 现在公认的最好的方法解决最短路径问题，是由E.W.Dijkstra，1959年提出的，也就是俗称的Dijkstra算法，他的名字命名的标记方法。该算法是基于这样一种想法，一种解释的几十种不同的优化算法更好的算法TQQ(graph growth with two queues),DKA(the Dijkstra`algorithm implemented with approximate buckets),DKD(the Dijkstra`s algorithm implemented with double buckets)，排序的优化算法，前面的三种算法中，空间储存的问题是非常重要的，牺牲适当的时间效率，来节省空间，排序优化算法放在了一个重要的位置上，可以更好地提高时间效率。其中TQQ算法依靠的是图增长理论，直线了两个FIFO队列与一个双端队列结构来支持搜索过程，更适合于计算单源点到所有其他点的最短距离。后两种算法在Dijkstra算法的基础上，使用桶结构，大大提高了对永久标记点的搜索速度。所以本课题主要采用的就是Dijkstra算法，使之可以应用于地铁站台，作出最短路径的选择。 (责任编辑：qin) |