Dijkstra算法

朱雀 2022-04-11 07:19 217阅读 0赞

# 算法描述 #

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

# 步骤 #

a.初始时，S只包含源点，即S＝\{v\}，v的距离为0。U包含除v外的其他顶点，即:U=\{其余顶点\}，若v与U中顶点u有边，则\{u,v\}正常有权值，若u不是v的出边邻接点，则\{u,v\}权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

# 执行动画： #

![这里写图片描述][20160902135240470]

# 具体的实例： #

![这里写图片描述][20160902135319221]

# 实例的步骤： #

![这里写图片描述][20160902135345033]  
参考：  
july的博客：  
[http://blog.csdn.net/v\_JULY\_v/article/details/6096981][http_blog.csdn.net_v_JULY_v_article_details_6096981]  
其他：  
[http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn][http_baike.baidu.com_view_1712262.htm_fromtitle_Dijkstra_E7_AE_97_E6_B3_95_fromid_215612_type_syn]  
[http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html][http_www.cnblogs.com_biyeymyhjob_archive_2012_07_31_2615833.html]

# #

[20160902135240470]: /images/20220411/749ed494e1154d6794fa134a11d31c90.png
[20160902135319221]: /images/20220411/b43b68487f034438bf87031b264a0d3d.png
[20160902135345033]: /images/20220411/1848634d7e6b4621850588131adb3257.png
[http_blog.csdn.net_v_JULY_v_article_details_6096981]: http://blog.csdn.net/v_JULY_v/article/details/6096981
[http_baike.baidu.com_view_1712262.htm_fromtitle_Dijkstra_E7_AE_97_E6_B3_95_fromid_215612_type_syn]: http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn
[http_www.cnblogs.com_biyeymyhjob_archive_2012_07_31_2615833.html]: http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html