哪里找做网站的客户,1 建设网站目的,wordpress不能视频,企业管理软件属于系统软件吗几大最短路径算法比较 转自#xff1a;http://blog.csdn.net/v_july_v/article/details/6181485 几个最短路径算法的比较#xff1a;Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差#xff0c;时间复杂度O(V^3)。 Floyd-Warshall算法#xff08;Floyd-W… 几大最短路径算法比较 转自http://blog.csdn.net/v_july_v/article/details/6181485 几个最短路径算法的比较Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差时间复杂度O(V^3)。 Floyd-Warshall算法Floyd-Warshall algorithm是解决任意两点间的最短路径的一种算法可以正确处理有向图或负权的最短路径问题。 Floyd-Warshall算法的时间复杂度为O(N^3)空间复杂度为O(N^2)。 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为 ∞ 表示两点之间没有任何连接。 Dijkstra 求单源、无负权的最短路。时效性较好时间复杂度为OV*VE。 源点可达的话OV*lgVE*lgVOE*lgV。 当是稀疏图的情况时此时EV*V/lgV所以算法的时间复杂度可为OV^2 。若是斐波那契堆作优先队列的话算法时间复杂度则为OV*lgV E。 更多请参考二续、彻底理解Dijkstra算法及二再续、Dijkstra 算法fibonacci堆的逐步c实现。 Bellman-Ford 求单源最短路可以判断有无负权回路若有则不存在最短路 时效性较好时间复杂度OVE。此算法日后还会在本BLOG内具体阐述。 Bellman-Ford算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指 给定一个加权有向图G和源点s对于图G中的任意一点v求从s到v的最短路径。 与Dijkstra算法不同的是在Bellman-Ford算法中边的权值可以为负数。 设想从我们可以从图中找到一个环路即从v出发经过若干个点之后又回到v且这个环路中所有边的权值之和为负。那么通过这个环路环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。 SPFA 是Bellman-Ford的队列优化时效性相对好时间复杂度OkE。kV。 与Bellman-ford算法类似SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是SPFA算法通过维护一个队列使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点从而大大减少了重复的操作次数。 SPFA算法可以用于存在负数边权的图这与dijkstra算法是不同的。 与Dijkstra算法与Bellman-ford算法都不同SPFA的算法时间效率是不稳定的即它对于不同的图所需要的时间有很大的差别。 在最好情形下每一个节点都只入队一次则算法实际上变为广度优先遍历其时间复杂度仅为O(E)。另一方面存在这样的例子使得每一个节点都被入队(V-1)次此时算法退化为Bellman-ford算法其时间复杂度为O(VE)。 SPFA算法在负边权图上可以完全取代Bellman-ford算法另外在稀疏图中也表现良好。但是在非负边权图中为了避免最坏情况的出现通常使用效率更加稳定的Dijkstra算法以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。 完。 转载于:https://www.cnblogs.com/AndyDai/p/4734120.html
