二四：最短路径问题：Dijkstra和Floyd算法详细描述
前言
- 最短路径的算法有两个，Dijkstra算法 和 Floyd算法。
- Dijkstra算法 解决的是 单源 最短路径问题。
- Floyd算法解决的是 多源 最短路径问题，并且可以处理负权图。
- 今天要讲的就是Dijkstra算法。
- 代码位置：https://github.com/fengfanli/dataStructuresAndAlgorithm/tree/master/src/com/feng/algorithm/self_learn
一、单源最短路径
1、单源最短路径问题
- 解决的问题: 求解单源最短路径,即各个节点到达源点的最短路径或权值。如下图中
考察其他所有节点到源点的最短路径和长度 - 局限性: 无法解决权值为负数的情况
- 资料
- 可先看匹配视频：https://www.bilibili.com/video/BV1o44y1B7NM/
- 代码：待上传。
2、Dijkstra 初始化
首先已知的是：
给定 邻接矩阵表示的图Graph、源点S、终点T。
a、参数
参数:
| 参数名 | 解释 |
|---|---|
| S | 记录当前已经处理过的源点到最短节点 |
| U | 记录还未处理的节点 |
| dist[] | 记录各个节点到起始节点的最短权值 |
| path[] | 记录各个节点的上一级节点(用来联系该节点到起始节点的路径) |
b、初始化参数
- 顶点集S: 节点A到自已的最短路径长度为0。只包含源点，即S={A}，代码中没有这个，这里是为了步骤清晰而设置的。