数据结构（九）——最短路径问题

文章目录

• 1. 单元最短路径问题

• • 1.1 BFS
  • 1.2 Dijkstra

• 2. 每对顶点间的最短路径

• • 2.1 Floyd

• 加权距离 ：任意一对顶点间的加权距离。

  • 最短路径 ：具有最小加权距离的一条路径。

最短路径问题一般可以分为两类，每一类都有经典的算法求解：

• 单一来源的最短路径问题：广度优先搜索用于解决无权图中的最短路径问题；而Dijkstra算法则适用于处理带权图中的最短路径问题。
  • 任意两节点之间的最短路径问题：Floyd算法能够处理带权重的图、不带权重的图以及存在负权重边的情况。

1. 单元最短路径问题

1.1 BFS

（1）算法思路
对于无权图，在一次BFS遍历中即可有效率地获得指定初始顶点的单源最短路径。相较于普通BFS算法而言，该方法另需维护d[N]和path[N]两个数组来分别存储与初始顶点间的最短距离以及构成最短路径的前驱顶点序列。

1. 设置变量d[N]和path[N]为初始状态。
2. 确定初始顶点，并将其直接相连的顶点的最短距离设为0。
3. 在层次遍历算法中，在处理每个节点时，在将邻近顶点加入队列之前更新其直接相连的顶点的最短距离以及前缀数组的状态。

    #define INT_MAX 3ff