狄克斯特拉算法

  • A+

图的最短路径算法,啊?广度优先搜索不就是求最短路径吗?好吧,广度优先搜索是求的最短节点数到达,但是每个节点到每个节点的距离(权重)不一样,就好比东莞到惠州和东莞到北京。所以这时候就要用迪克斯特拉算法了。

 


一、首先,是点和边

一个图,可以这样说吧,就是有点(节点),边(节点之间的关系)构成的,这里的边,有一个权重值,就是用来衡量这个边(节点到节点的成本,两地的距离)。下面就用这些来构建一个图。

 


二、构建权重图(测试用的数据)

这里构建了四个点,还有O到A,O到B,B到A,B到C,A到C,5条边。看图,还有权重值,找出权重值总和最小的路径都参考此图

狄克斯特拉算法


三、获取目前路径总权重最小的结点数据

每步最优解啊,所以遍历路径来找到那个权重最小的路径,已经访问过的就不用再去访问啦,不然可能死循环咯

 


四、主函数

这里是主要的功能函数。首先,当然是要从起点开始啦,先初始化字典,就是起点到临近结点的距离(路径),到终点的路径距离是不知道的,所以先设为无穷(这里用Int32的最大值表示)。随后就是一直重复做的事情了。主要思想就是先获取路径中最小权重的路径,访问它的尾结点到其他所有结点的总权重(加起来),再去更新路径(如果有更近的到达方案或者是这个结点没有到达过),记得也要更新父节点字典啊,它主要记录的是最短到达本节点的路径的父节点(上一个节点)。所以,最后的时候就可以通过父节点字典从终点,一直访问父节点得到最短路径了

 


五、结果

狄克斯特拉算法

 


注意:图不能出现环图(2个或两个结点可以绕圈圈到达),也不能出现负权重,权重只是表达该路径的大小长短等价值值,很容易控制,而环图就需要注意了

 

完整代码

 

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: