迪杰斯特拉算法_【每周算法】迪杰斯特拉算法（Dijkstra#39;sAlgorithm）

算法简介

不要当背景故事跳过了哦

01

    迪杰斯特拉算法是典型的最短路径的算法&＃xff0c;由荷兰计算机科学家迪杰斯特拉于1959年提出&＃xff0c;用来求得从起始点到其他所有点最短路径。

    该算法采用了贪心的思想&＃xff0c;每次都查找与该点距离最近的点(也因为这样&＃xff0c;它不能用来解决存在负权边的图)。

    解决的问题可描述为&＃xff1a;在无向图 G&＃61;(V,E) 中&＃xff0c;假设每条边 E[i] 的长度为 w[i]&＃xff0c;找到由顶点vs到其余各点的最短路径。

02

基本思路

开始迷茫

贰

假装是一个标题

假装是一个没有灵魂的副标题

    我们所需要考虑的点有两种&＃xff0c;一种是已经计算过的点&＃xff0c;一种是未计算过的点&＃xff0c;并且还要储存顶点到他们的最短距离。

   以下图为例&＃xff0c;先设立两个集合S和U&＃xff0c;S中包含以计算的点与到此点的最短距离&＃xff0c;U中包含未计算的点以及该点到顶点的距离。设定A的出边临界点距离为原值&＃xff0c;不是的为无穷大。

    开始运算时&＃xff0c;S中只包含了顶点(下图中的A)&＃xff0c;而U中包含了剩余未计算的点(下图中A以外的点)。然后开始进行运算&＃xff0c;先以A为中心点开始寻找&＃xff0c;在U中找到A的出边临界点(B和C)&＃xff0c;并计算他们与A的距离&＃xff0c;将距离最短的点(C)从U集合取出放入S集合中&＃xff0c;并更新S中A到各点的最短距离&＃xff0c;再以上一个被取到S的点(C)作为中心点&＃xff0c;重复进行上一步操作&＃xff0c;直到U中没有点元素。

算法步骤

彻底失智

03

    还是以那个无向图为例

    a.初始时&＃xff0c;S只包含源点&＃xff0c;即S&＃xff1d;{vs}&＃xff0c;vs的距离为0。U包含除vs外的其他顶点&＃xff0c;即U&＃61;{其余顶点}&＃xff0c;若u不是vs的出边邻接点&＃xff0c;则权值为∞&＃xff1b;

    b.从U中选取一个距离vs最小的顶点k&＃xff0c;把k加入S中(该选定的距离就是vs到k的最短路径长度min)&＃xff1b;以k为新考虑的中间点&＃xff0c;修改U中各顶点的距离&＃xff1b;若从源点vs到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短&＃xff0c;则修改顶点u的距离值&＃xff0c;即dist[u] &＃61; min( dist[u], min &＃43; w[k][u] )&＃xff1b;

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

   迪杰斯特拉算法是很基础但也很重要的一种算法&＃xff0c;例如著名的A*算法便是迪杰斯特拉算法的延伸&＃xff0c;所以此算法的重要性不言而喻&＃xff0c;希望各位小伙伴们都会认真学习下这个算法(虽然大家可能已经都会了)&＃xff01;

参考链接&＃xff1a;https://www.cnblogs.com/21207-iHome/p/6048969.html