- 浏览: 250450 次
- 性别:
- 来自: 苏州
文章分类
- 全部博客 (289)
- java (72)
- oracle (3)
- mysql (5)
- spring (28)
- hibernate (2)
- osgi (0)
- linux (2)
- ExtJs (1)
- jvm (0)
- mybatis (7)
- 分布式 (11)
- MINA (6)
- apache+tomcat (13)
- js+htm (7)
- android (44)
- http (1)
- hbase+hdoop (0)
- memcache (13)
- search (27)
- 部署及性能 (12)
- mongoDB (2)
- 多线程 (12)
- 安全管理验证 (9)
- struts (1)
- webservice (0)
- easyUI (1)
- spring security (16)
- pattern (6)
- 算法 (2)
最新评论
-
lzh8189146:
CommonsHttpSolrServer这个类,现在是不是没 ...
CommonsHttpSolrServer -
xiaochanzi:
我按照你的方法试了下,tomcat6可以发布,但是访问任何网页 ...
基于内嵌Tomcat的应用开发 -
phoneeye:
麻烦你,如果是抄来的文章,请给出来源。谢谢
ant 两则技巧 -
neverforget:
转载不注明出处
Spring Security3.1登陆验证 替换 usernamepasswordfilter -
liang1022:
若不使用eclipse ,如何在命令行下 运行服务端程序 ?
WebService CXF学习(入门篇2):HelloWorld
Dijkstra算法是典型的最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等。
Dijkstra算法思想为:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径,就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
(1)初始时,S只包含源点,即S=,v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边)或(若u不是v的出边邻接点)。
(2)从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
(3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u(u U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。
(4)重复步骤(2)和(3),直到所有顶点都包含在S中。
Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。
举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 假设E为所有边的集合,而边的权重则由权重函数w: E → [0, ∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者是无穷大(如果路径不存在的话)。
Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是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)进 行拓展。
算法思想
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。①初始化
初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空。
②重复以下工作,按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证按路径权重递增的次序来产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:
①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。
(3)在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想,当前最短距离最小的蓝点k的最短路径是:
源点,红点1,红点2,…,红点n,蓝点k
距离为:源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便,设置一个向量D[0..n-1],对于每个蓝点v∈ V-S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的"最短"路径长度(简称估计距离)。
若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min{D[i] i∈V-S},则D[k]=SD(k)。
初始时,每个蓝点v的D[c]值应为权w<s,v>,且从s到v的路径上没有中间点,因为该路径仅含一条边<s,v>。
注意:
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
(4)k扩充红点集s后,蓝点集估计距离的修改
将k扩充到红点后,剩余蓝点集的估计距离可能由于增加了新红点k而减小,此时必须调整相应蓝点的估计距离。
对于任意的蓝点j,若k由蓝变红后使D[j]变小,则必定是由于存在一条从s到j且包含新红点k的更短路径:P=<s,…,k,j>。且D [j]减小的新路径P只可能是由于路径<s,…,k>和边<k,j>组成。
所以,当length(P)=D[k]+w<k,j>小于D[j]时,应该用P的长度来修改D[j]的值。
(5)Dijkstra算法
Dijkstra(G,D,s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s};D[s]=0; //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]; //设置i初始的估计距离为w<s,i>
//以下是扩充红点集
for(i=0;i<n-1;i++)do{//最多扩充n-1个蓝点到红点集
D[k]=min{D[i]:all i V-S}; //在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞)
return; //蓝点集中所有蓝点的估计距离均为∞时,
//表示这些顶点的最短路径不存在。
S=S∪{k}; //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时,用新路径的长度修改D[j],
//使j离s更近。
D[j]=D[k]+G[k][j];
}
}
发表评论
-
Java keytool 安全证书学习笔记
2012-08-02 14:16 760http://linliangyi2007.iteye.com ... -
java国际化
2012-07-16 14:08 381http://lavasoft.blog.51cto.com/ ... -
Java版远程控制V1.0
2012-06-17 21:37 713http://www.cnblogs.com/syxchina ... -
浅析Java中CountDownLatch用法
2012-05-16 20:57 767CountDownLatch如其所写,是一个 ... -
SMTP发送邮件
2012-04-18 09:41 728SMTP发送邮件 openkk 2011-06-0 ... -
smtp 返回代码 信息
2012-04-18 08:52 1416SMTP Server Response Cod ... -
JavaMail详解
2012-04-18 02:24 0JavaMail详解 博客分类: JAV ... -
安装Eclipse反编译插件
2012-04-17 09:34 779安装Eclipse反编译插件 博客分类: ... -
Java编程中“为了性能”尽量要做到的一些地方
2012-04-13 08:30 641最近的机器内存又爆满了,除了新增机器内存外,还应该好好r ... -
java 播放音乐
2012-04-11 08:00 974java 播放音乐 博客分类: J2 ... -
Java中的native,transient,volatile和strictfp关键字
2012-04-06 08:49 707Java中的native,transient,v ... -
用ReentrantLock模拟宴会的热闹情景
2012-04-05 08:32 876用ReentrantLock模拟宴会的热闹情景 ... -
Hashmap 分析
2012-04-05 08:32 702Hashmap 博客分类: 算法 ... -
ExecutorService线程池
2012-04-05 08:32 732ExecutorService线程池 (2010 ... -
Java并发:juc Executor框架详解
2012-04-05 08:32 739Java并发:juc Executor ... -
java并发包,多线程,工具类,笔记
2012-04-11 08:00 864JDK 线程池 Executors.newCachedT ... -
利用 Spring 和 EHCache 做方法缓存处理〔转〕
2012-04-09 09:49 801利用 Spring 和 EHCache 做方法缓存处理〔 ... -
EhCache使用详细介绍
2012-04-09 09:49 1324EhCache使用详细介绍 Ehcache中不仅可 ... -
HashMap 分析
2012-04-01 08:21 1865http://www.blogjava.net ... -
Java IOC设计模式
2012-04-01 08:21 751Java IOC设计模式 IoC模式简介 ...
相关推荐
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
dijkstra算法C++实现的程序代码
毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向...
能够实现 Dijkstra算法,内涵代码,运行即可实现
Dijkstra算法应用举例 Dijkstra算法应用举例Dijkstra算法应用举例 Dijkstra算法应用举例
本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。
文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作...
Dijkstra算法求解格栅地图路径matlab代码
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
Dijkstra算法的应用, Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向...对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。
C语言版Dijkstra算法,有注释。 只是简单的Dijkstra算法的实现。
Dijkstra算法,Dijkstra算法详细讲解,Dijkstra算法详细讲解
Dijkstra算法是用于计算一个节点到其余所有节点最短路径的单源路径算法。我们先阐述Dijkstra算法的原理,在算法设计中,分别用邻接矩阵和邻接表存储带权有向图,并编写C++语言实现Dijkstra算法最短路径,用户只需...
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
主要使用了Dijkstra算法,Floyd算法。 主要功能有六项:1、烟台大学的平面图。2、景点的介绍。3、从一个景点到其他地方的所有最短路径。4、两景点间的最短路径。5、计算从一个地方到另一个地方所要花费的时间。6、...
Dijkstra算法求最短路径的C/C++程序