Dijkstra 最短路径算法

Dijkstra算法的核心点是贪心算法：不断寻找最短的点，在最短的点上更新最短路径

1.前言

想要了解学习Dijkstra算法，需要先了解无向图与权重图，无向图顾名思义就是没有方向的图，下面表示了有向图和无向图以及权重图

2.什么是Dijkstra算法

Dijkstra 算法，可以寻找图中节点之间的最短路径。特别是，可以在图中寻找一个节点（称为“源节点”）到所有其它节点的最短路径，生成一个最短路径树。荷兰杰出计算机科学家、软件工程师 Dr.Edsger W.Dijkstra创建并发布了这个算法。
Dijkstra 算法的基础知识：

• Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径
• Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新
• 一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中
• 重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案

3.实现原理

假设存在这样一个无向图，求P0点到其他点的最短距离

3.1 P0为起点

3.2 P1为起点

3.3 P3为起点

3.4 P4为起点

3.5 P6为起点

最终得到了P0到其他各个点的最短距离：
P0(0),P1(2),P2(6),P3(7),P4(17),P5(22),P6(19)

引用链接：
【1】图文详解 Dijkstra 最短路径算法
【2】最短路径算法-迪杰斯特拉(Dijkstra)算法