迪杰斯特拉算法不懂?看严蔚敏的书还是看不懂?就看这篇文章吧,博主我一大优点就是表述能力比较强。也就是说,要么我自己不懂,我懂了以后一定能让别人弄懂。
迪杰斯特拉算法是典型最短路径算法,用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外,层层扩展,直到扩展覆盖所有顶点。
2,迪杰斯特拉算法思想
设G=(V,E)为一个带全有向图,把图中顶点集合V分成两组。第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将所到达最短路径的顶点加入到集合S中,直到全部顶点都加入到S中)。第二组为其余未确定最短路径的顶点集合(用U表示,U=V-S,U中的顶点不断的加入到S中,直到U为空,S=V)。在U加入S的过程中,始终保持源点到S中各顶点的最短路径长度小于或等于源点到U中任意顶点的最短路径长度。
3,迪杰斯特拉算法执行步骤
设 n 为图 G=(V,E) 中的顶点数,dist[n] 存放从源点到每个终点当前最短路径的长度,path[n] 存放相应路径,S 为已求得最短路径的终点的集合,U为V-S,初始为不含有源点的所有顶点。
(1)初始化已求的最短路径的集合S为只含有元素源点a,S={a}。
(2)从U中选取一个距离源点v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
(3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u(u U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值为顶点k的距离加上顶点k到u边上的权。
(4)重复步骤(2)和(3)直到所有顶点都包含在S中。
4,迪杰斯特拉算法举例说明
(1)有向图如下,以a为源点,求源点a到其他各顶点的最短路径。
(2)算法详细步骤如下表:
步骤
|
S集合中
|
U集合中
|
初始化
|
选入a,此时s={a}
此时最短路径有a->a=0
以a为中间点,从a开始找
|
U={b,c,d,e,f}
a->b=1
a->c=2
a->e=15
a->其他U中顶点为无穷
|
1
|
从U={b,c,d,e,f}中发现路径a->b=1最短
选入b,S={a,b}
此时最短路径有a->a=0,a->b=1
以b为中间点,从a->b=1这条最短路径开始找
|
U={c,d,e,f}
(a->b->d=7)<初始的无穷
改写a->b->d=无穷为当前的a->b->d=7
a-> b->其他U中顶点为无穷
|
2
|
从U={c,d,e,f}中发现路径a->c=2最短
选入c,S={a,b,c}
此时最短路径有
a->a=0,a->b=1,a->c=2
以b为中间点,从a->c=2这条最短路径开始找
|
U={d,e,f}
(a->c->d=5)<已有的7
改写为a->c->d=5
|
3
|
从U={d,e,f}中发现路径a->c->d=5最短
选入d,S={a,b,c,d}
此时最短路径有
a->a=0,a->b=1,a->c=2,a->c->d=5
以d为中间点,从a->c->d=5这条最短路径开始找
|
U={e,f}
(a->c->d->e=9)<步骤1中的15
改写为a->c->d->e=9
(a->c->d->f=6)<初始的无穷
改写为a->c->d->f=6
|
4
|
从U={e,f}中发现路径a->c->d->f=6最短
选入f,S={a,b,c,d,f}
此时最短路径有
a->a=0,a->b=1,a->c=2,a->c->d=5
a->c->d->f=6
以f为中间点,从a->c->d->f=6这条最短路径开始找
|
U={e}
(a->c->d->f->e=7)<步骤3中改写成的9
改写为a->c->d->f->e=7
|
5
|
从U={f}中发现路径a->c->d->f->e=7最短
选入f,S={a,b,c,d,f,e}
此时最短路径有
a->a=0,a->b=1,a->c=2,a->c->d=5
a->c->d->f=6,a->c->d->f->e=7
|
U集合已空,查找完毕。
|
参考文献:
[1], http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/
[2],严蔚敏,数据结构(电子版),清华大学出版社。
算法如下:(下载自百度文库,略微修改)
分享到:
相关推荐
实现迪杰斯特拉算法 Dijkstra void main() { //设置初值 int u=1; //设源点的序号为1 for(int i=0; i; i++) { Visited[i]=0; path[i]=u-1; Distance[i]=Graph[u-1][i]; } Visited[u-1]=1; //源点已...
期末数据库课程设计 《火车出行路线规划及售票系统》 利用迪杰斯特拉算法找到最省钱的城市路线(只是城市路线) 采用简单工厂模式进行设计用户操作
迪杰斯特拉算法算法步骤: (1)初始时,S只包含源点。 (2)从U中选取一个距离v最小的顶点k加入S中(该选定的距离就是v到k的最短路径长度)。 (3)以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到...
迪杰斯特拉算法的Java实现
实现最小生成树 最短路径 floyd 广搜 深搜 迪杰斯特拉算法
数据结构中的关键路径实现,可视化界面,迪杰斯特拉算法,和弗洛伊德算法
最短路问题迪杰斯特拉算法PPT课件.pptx
单源最短路径 贝尔曼福特 和 迪杰斯特拉 算法的实现
数据结构与算法中图求最短路径,迪杰斯特拉算法的实现,带详细注释,可完整实现。
用MATLAB实现迪杰斯特拉算法来寻找最短路径,压缩包中DIJ为算法的执行程序,SymMatrix为将邻接矩阵补齐为对称矩阵的程序,两个graph文件存储的两个邻接矩阵,DIJ加载了其中一个进行计算。也可以自己重新编辑邻接矩阵...
def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径,并返回该路径和代价 print(Start Dijstra Path……) path=[]#s-d的最短路径 n=len(network)#邻接矩阵维度,即节点个数 fmax=999 w=[[0 for i in ...
C语言实现迪杰斯特拉算法,亲测好用,放在正确的环境下就可运行
迪杰斯特拉算法景点问题C语言
迪杰斯特拉算法或者floyd算法,我不记得具体是哪个了,但肯定是生成最短路径矩阵的函数
通过邻接矩阵的数据结构存储一副图结构。利用迪杰斯特拉算法(C++实现)求其最短路径。
自己用c语言写的迪杰斯特拉算法,存储方式为邻接矩阵表示法
迪杰斯特拉算法有详细的试验报告 可以动态演示,已通过课程设计,资源特别棒 下载不后悔
用C写的迪杰斯特拉算法,很简单,希望能对大家有帮助
用python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
matlab编写迪杰斯特拉算法求解求最短路问题,文件是程序源代码