五大最短路径算法比较
July、二零一一年二月十二日。
本文参考:维基百科。
-----------------------------------
几个最短路径算法的比较:
I、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为 ∞ 表示两点之间没有任何连接。
II、Dijkstra:求单源、无负权的最短路。时效性较好,时间复杂度为O(V*V+E)。
源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)。
当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为O(V^2) 。
若是斐波那契堆作优先队列的话,算法时间复杂度,则为O(V*lgV + E)。
更多,请参考:经典算法研究系列:二、Dijkstra 算法
http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx
III、Bellman-Ford:求单源最短路,可以判断有无负权回路(若有,则不存在最短路),
时效性较好,时间复杂度O(VE)。此算法日后还会在本BLOG内具体阐述。
Bellman-Ford算法是求解单源最短路径问题的一种算法。
单源点的最短路径问题是指:
给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。
与Dijkstra算法不同的是,在Bellman-Ford算法中,边的权值可以为负数。
设想从我们可以从图中找到一个环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有边的权值之和为负。
那么通过这个环路,环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。
IV、SPFA:是Bellman-Ford的队列优化,时效性相对好,时间复杂度O(kE)。(k<<V)。
与Bellman-ford算法类似,SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是,SPFA算法通过维护一个队列,使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点,从而大大减少了重复的操作次数。
SPFA算法可以用于存在负数边权的图,这与dijkstra算法是不同的。
与Dijkstra算法与Bellman-ford算法都不同,
SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。
在最好情形下,每一个节点都只入队一次,则算法实际上变为广度优先遍历,其时间复杂度仅为O(E)。另一方面,存在这样的例子,使得每一个节点都被入队(V-1)次,此时算法退化为Bellman-ford算法,其时间复杂度为O(VE)。
SPFA算法在负边权图上可以完全取代Bellman-ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。
V、宽搜:求单源无权最短路。矩阵记录法时间复杂度O(V^2);边表记录法时间复杂度O(kE)。
本人July对本博客所有任何文章、内容和资料享有版权。
转载务必注明作者本人及出处,并通知本人。July、二零一一年二月十二日。
分享到:
相关推荐
这个小例子展示了如何使用C#编程语言来实现一个最短路径算法。最短路径问题通常涉及到在一个加权图中寻找从一个源节点到其他所有节点的最短路径。这里我们将探讨几种常见的最短路径算法,并且会提及如何用C#来实现...
这个问题可以用图论中的最短路径算法来解决。 **定义**: - **图**:在计算机科学中,图是一种数据结构,由一系列的节点(顶点)和连接这些节点的边组成。 - **权重**:每条边都有一个数值,称为权重,用来表示两点...
以下是对几种常见最短路径算法的详细讲解: 1. **迪杰斯特拉算法 (Dijkstra's Algorithm)** 迪杰斯特拉算法是一种单源最短路径算法,它能找出从一个指定起始节点到图中所有其他节点的最短路径。算法基于贪心策略,...
在给定的“经过指定节点的最短路径算法GUI程序”中,我们主要讨论的是如何设计一个图形用户界面(GUI)来实现寻找图中经过特定节点的最短路径问题。以下是对这个主题的详细解释: 1. **最短路径算法**:最短路径...
对于含障碍的两点最短路径算法,通常有以下几种可能的实现方式: 1. **A* 搜索算法**:尽管描述中排除了Dijkstra,但A* 算法可以考虑障碍因素,并通过启发式函数来指导搜索,找到更高效的路径。在MATLAB中,可以...
### 基于地理信息系统的最短路径算法 #### 概述 最短路径问题(Shortest Path Problem, SP)是人工智能领域中的一个重要研究方向,它不仅在理论上有着丰富的研究内容,在实际应用中也极为广泛,尤其是在交通网络...
### 第k条最短路径算法知识点详解 #### 一、引言 在现代网络和通信领域,寻找两点之间的最短路径是一项基本而重要的任务。传统的单源最短路径算法(如Dijkstra算法)只能找到从起点到终点的单一最短路径。然而,在...
该最短路径算法主要以南京市的道路交通为模板(具体见附录图1) 简单实现任意两个地点之间最短路径查询(例如三牌楼 新街口) 该最短路径剔除了那些由于某些原因堵塞不通的路径 有很好的图形界面便于人机交互 路径...
本篇将重点介绍如何使用C语言来实现最短路径算法,并探讨几种常见的算法。 1. **Dijkstra算法** Dijkstra算法是最常用的单源最短路径算法,适用于有权图。它的基本思想是从起点开始,逐步扩展最短路径树,直到覆盖...
这里,我们主要探讨几种常见的最短路径算法及其原理。 1. **Dijkstra算法**:由荷兰计算机科学家艾兹格·迪科斯彻提出,适用于有向图或无向图,且边的权重非负。Dijkstra算法采用贪心策略,逐步扩展最短路径树,...
### 最短路径算法的改进与实现 #### 一、最短路径问题的研究背景及应用场景 最短路径问题作为图论中的一个重要课题,在诸多领域中都有着广泛的应用,包括但不限于交通运输、网络寻优等领域。该问题的核心在于寻找...
### 基于GIS的城市道路网最短路径算法优化 #### 概述 在现代城市交通管理中,寻找从一个地点到另一个地点的最短路径是一个至关重要的问题。这一问题不仅涉及交通规划、物流配送等领域,而且对于提高城市交通效率、...
【最短路径算法】 在计算机科学中,最短路径算法是一种用于寻找图中两点之间最短路径的方法。这里提到的算法是Dijkstra算法,一种贪心算法,它能有效地找到加权无向图中单个起点到所有其他顶点的最短路径。Dijkstra...
迪杰斯特拉(Dijkstra)最短路径算法是图论中的一个重要算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于寻找图中两个节点之间的最短路径,特别适用于加权有向图。在VB.NET中实现Dijkstra...
Dijkstra最短路径算法是一种经典的图论算法,用于寻找图中一个节点到其他所有节点的最短路径。在计算机科学中,特别是在网络路由、图形算法和路径搜索等领域有着广泛的应用。C语言作为基础且高效的编程语言,是实现...
Java编写的单元最短路径算法,是解决图论问题中的一种经典方法,主要用来寻找网络中的最短路径。在这个场景中,我们关注的是Dijkstra算法,这是一种贪心算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。它能...
在WinForm项目中实现图和最短路径算法,你需要做以下几步: 1. 设计图形界面:使用WinForm控件如PictureBox或自定义控件来显示图,可能需要绘制点和线来表示顶点和边。 2. 存储和操作图数据:定义一个数据结构来...
本篇将深入探讨如何利用VC++实现最短路径算法,以及涉及到的数据结构。 最短路径问题通常在有向或无向图中出现,寻找从一个特定起点(源节点)到其他所有节点的最短路径。在标题"vc++实现最短路径算法"中,我们关注...
迪杰斯特拉(Dijkstra)算法是一种用于寻找图中两个节点间最短路径的算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要应用于单源最短路径问题,即从一个源节点出发找到到图中所有其他节点的...