Dijkstra算法
给定一个出发点，到其他每一个点的最短路径是什么
image.png

跟最小生成树算法不同：

  • k算法和p算法过程是：如果从给定的点出发，形成联通区域，整体权重和最小值，
  • D算法要求是从起始点到每个节点距离最小，要求更强，

比如下面图的例子，如果按照k算法，abc形成集合，下一个边选对外最小的7这条边，但是对于a来说，到d最短的路是9
这样，仅仅形成联通区域的边虽然小，但是舍弃掉了。

  • 同时我们也总结除了D算法的步骤，就是加入一条边的时候，判断a到这条边起点的最短距离加上边权重是否小于从a到d的距离

也是一种贪心思想。
tips：a*算法是一种启发式算法，比D算法好一些，但有限，不是做图像的很难用到。
image.png
image.png

解法1：

step1: 初始化
image.png
step2 ：
image.png
step3 ： 框起来的实际上锁死了，以后再也不更新了。
image.png

step4:
image.png
注意：一定要求权重没有负数的
image.png
代码：
map指的就是上图右下角的最短距离结构，从head出发的最短距离
没有记录表示正无穷。
step1 ： 初始化从跟节点到每个节点的最短距离，只有自己是0
step2: 从中发现距离最短的，且没有被锁死的节点。
image.png
step3：对于选中的节点，在所有出边上，判断end对应的当前距离和 从该点沿着出边权重到达end的距离较小值，更新。
image.png
image.png
改进： 改写堆的问题，D算法有一个堆的优化，这个忘了；
遍历的方式选出来最小值，在distanceMap中，如果用堆的化，加入到堆，当改变了一个值之后，原始提供的优先队列无法
自动调整堆结构，每次锁死的节点直接弹出也行吧
左程云：

  • 假设从F往外跳，较大的值变成较小的值，系统提供的函数在修改一个元素的值的以后，调整代价挺高。没有heapify的操作。
  • 如果题目是老老实实给一个值吐一个值，那么系统提供的就行，如果中间碰到要修改值，还希望保持大根堆结构，那么要自己改写。

image.png

问题：能不能把沿途的路径给求出来。
维护一个字典，当更新的时候把节点加上。

解法2 ：改写堆加速

image.png