路径规划算法学习Day1

  • 前言
  • Dijkstra算法
    • 一、基本思想
    • 二、定义
    • 例一:找出结点a到其它结点的最短路径
      • 初始化
      • 算法详解

前言


解决最短路径问题的算法有很多,Dijkstra算法是其中最为有效的一种。
它是于1959年荷兰计算机科学家EDsger Dijkstra提出的:能够解决----“单结点——>所有结点”间的最短路径问题。

Dijkstra算法

一、基本思想

首先以某一结点(源结点)作为出发点,在与其相连且尚未被加入的结点里,选择加入离出发点距离最短的结点,并且通过新加入的结点更新出发点到其它结点的距离。如此重复加入新结点,直到所有结点都被加入为止。

二、定义

—s:源结点,例如结点a;
—d(j):从源结点到目的结点j的当前最短路径;
—p(j):从源结点到目的结点j的最短路径中,结点j的前继结点(也就是j前面那个点);
—k:新加入的结点;

例一:找出结点a到其它结点的最短路径

在这里插入图片描述

初始化

1.选择源结点为a;
2.k=a,即新加入的结点为a
3.d(a)=0,对于其他结点j,d(j)=∞;
4.p(a)为起始符号 (例如*),对于其它结点j,p(j)为空;
在这里插入图片描述

算法详解

第一次循环:
1.更新距离:d(b)=3<∞ d©=8<∞ d(d)=5<∞;
2.加入结点b:d(b)在未加入结点中最小;
3.k=b;
4.更新b的前继结点:p(b)=a;
表格表示为:
在这里插入图片描述
第二次循环:
(由于更新b为前继结点,所以从b出发+a到b的距离再与其它距离比较得出最短距离)
1.更新距离:d(f)=10(3+7<∞) d©=8(3+5<∞)
2.加入结点d:d(d)在未加入结点中最小;
3.k=d;
4.更新d的前继结点:p(d)=a;
表格表示为:
在这里插入图片描述
第三次循环:
1.更新距离:d(g)=9(5+4<∞) d©=7(5+2<8)
2.加入结点c:d(d)在未加入结点中最小;
3.k=c;
4.更新c的前继结点:p©=d;
表格表示为:
在这里插入图片描述
第四次循环:
1.更新距离:d(e)=15(7+8<∞) d(f)不变 (7+5>10);
2.加入结点g:d(g)在未加入结点中最小;
3.k=g;
4.更新g的前继结点:p(g)=d;
表格表示为:
在这里插入图片描述
第五次循环:
1.更新距离:d(i)=13(5+4+4<∞) d(e)不变 (9+6=15);
2.加入结点f:d(f)在未加入结点中最小;
3.k=f;
4.更新f的前继结点:p(f)=b;
表格表示为:
在这里插入图片描述

第六次循环:
1.更新距离:d(h)=16(10+6<∞) d(e)不变 (10+5=15);
2.加入结点i:d(i)在未加入结点中最小;
3.k=i;
4.更新i的前继结点:p(i)=g;
表格表示为:
在这里插入图片描述
第七次循环:
1.更新距离:d(j)=19(13+6<∞) d(e)=14 (13+1<15);
2.加入结点e:d(e)在未加入结点中最小;
3.k=e;
4.更新i的前继结点:p(e)=i;
表格表示为:
在这里插入图片描述
第八次循环:
1.更新距离:d(h)=15(14+1<16) d(e)=14 (13+1<15);
2.加入结点h:d(h)在未加入结点中最小;
3.k=h;
4.更新h的前继结点:p(h)=e;
表格表示为:
在这里插入图片描述
第九次循环:
1.更新距离:d(j)=17(15+2<19)
2.加入结点j:d(j)在未加入结点中最小;
3.k=j;
4.更新j的前继结点:p(j)=h;
表格表示为:
在这里插入图片描述
最短路径:
1.所有结点均被加入,算法结束;
2.d(i)为从结点a到任意结点i的最短路径的距离;
3.通过回溯p(i),可确定结点a到任意结点i的最短路径;
在这里插入图片描述
期待大家的点评,代码会在后面博文中给出,敬请期待!