7.6最短路径
对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点
7.6.1迪杰斯特拉(Dijkstra)算法
Dijkstra是用来求单源最短路径的
就拿上图来说，假如直到的路径和长度已知，那么可以使用dijkstra算法计算南京到图中所有节点的最短距离。
单源什么意思？
- 从一个顶点出发，Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。
摘自：
最短路径算法-迪杰斯特拉(Dijkstra)算法 - 知乎 (zhihu.com)
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想)，直到扩展到终点为止。
基本思想
- 通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
- 此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
- 初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
- 然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
- 重复第4步操作，直到遍历完所有顶点。
迪杰斯特拉(Dijkstra)算法图解
我在叠一层，哈哈哈
以上图为例，来对迪杰斯特拉进行算法演示(以顶点D为起点)。
看图很清晰了！
