04最短路径分析的算法—Dijkstra-算法.pptx

最短路径分析的算法——Dijkstra 算法
解决最短路径问题的算法很多, Dijkstra算法是最有效的算法之一:– Dijkstra算法 • 1959年,荷兰计算机科学家Edsger Dijkstra提出; •能够一次解决“单结点-所有结点”间的最短路径问题;
Dijkstra 算法
基本思想:
首先以某一结点(源结点)作为出发点,在与其相连且尚未被加入的结点里,选择加入离出发点距离最短的结点,并且通过新加入的结点更新出发点到其他结点的距离。如此重复加入新结点,直到所有的结点都被加入为止。
定义:
– s : 源结点, 例如结点a;
– d(j) : 从源节点到目的结点j的当前最短路径;
– p(j) : 从源结点到结点j的最短路径中,结点j的前继结点;
– k : 最新加入的结点;
例1 找出结点a到其他结点的最短路径
初始化:–选择源结点, 例如结点a;– k=a,即最新加入的结点为a– d(a)=0,对于其他结点j ,d(j)=∝;– p(a)为起始符号(例如﹡),对于其他结点j,p(j)为空;
第一次循环:–更新距离:d(b) =3(3<∝)、d(c) =8(8<∝)、 d(d) = 5(5<∝) ;–加入结点b: d(b) 在未加入结点中最小;– k = b;–更新b的前继结点: p(b) = a ;
第二次循环:–更新距离:d(f) =10(3+7<∝)、d(c) 不变(为什么?) ;–加入结点d: d(d)在未加入结点中最小;– k = d;–更新d的前继结点: p(d) = a ;
第三次循环:–更新距离:d(g) =9(5+4<∝)、d(c) = 7(5+2<8) ;–加入结点c: d(c)在未加入结点中最小;– k = c;–更新c的前继结点: p(c) = d ;
第四次循环:–更新距离:d(e) =15(7+8<∝)、d(f) 不变(7+5>10) ;–加入结点g: d(g)在未加入结点中最小;– k = g;–更新g的前继结点: p(g) = d ;