2024/08/03 真题讲解（最短路问题Floyd算法专题）

最短路问题概述

最短路问题（Shortest Path Problem）是图论中一个经典的问题，旨在找到从一个顶点到另一个顶点的最短路径。​

所给定的图可以是有向图（directed graph）也可以是无向图（undirected graph），并且边可以有权重（weights），即每条边有一个数值表示从一个顶点到另一个顶点的距离或成本。​

最短路问题的常见变种包括：

1.
单源最短路径问题：找到从图中某个特定顶点到所有其他顶点的最短路径。​

2.
单对最短路径问题：找到从图中某个特定顶点到另一个特定顶点的最短路径。​

3.
全源最短路径问题：找到图中每对顶点之间的最短路径。​

解决最短路问题通常有包含以下算法

1.
Dijkstra算法：​

•
定义：用于解决单源最短路径问题，适用于边权重非负的图。​

•
原理：通过贪心策略，逐步选择具有最小估计距离的顶点，并更新其邻接顶点的距离。​

•
时间复杂度：O((V + E) log V)，其中 V 是顶点数，E 是边数。​

2.
Bellman-Ford算法：​

•
定义：用于解决单源最短路径问题，可以处理负权重的边。​

•
原理：通过对所有边进行多次松弛操作，逐步逼近最短路径。​

•
时间复杂度：O(VE)，其中 V 是顶点数，E 是边数。​

3.
Floyd算法：​

•
定义：用于解决全源最短路径问题。​

•
原理：通过动态规划的方式，逐步考虑每个顶点作为中间点，更新所有顶点对之间的最短路径。​

•
时间复杂度：O(V^3)，其中 V 是顶点数。​

本篇讲解主要介绍Floyd算法的原理以及应用

带边权的图的全源最短路径

对于以下无向图，我们能够看到图中包含了若干节点以及节点之间的边权​

这里的边权可以简单理解为两个节点之间的距离

大部分题目（但不是绝对的）会用一个外层长度为m，内层长度为3的二维数组edges，来表无向图。​

其中m是整个图的边数，edges[i] = [start_i, end_i, w_i]，表示在第i条边中，start_i节点和end_i节点之间的距离为w_i。​

譬如，上述无向图可以用以下二维数组edges来表示

代码块

edges = [​
[0, 1, 2],​
[0, 4, 8],​
[1, 2, 3],​
[1, 4, 2],​
[2, 3, 1],​
[3, 4, 1]​
]​

2024/08/03 真题讲解（最短路问题Floyd算法专题）​