最短路径算法

完整版万字原文见史上最全详解图数据结构

1. Dijkstra算法（单源最短路径）（无负权边图）

---

算法原理

1. Dijkstra 算法通过 贪心策略 计算从一个源顶点到其他所有 顶点的最短路径。2. 时间复杂度为 O(V^2)（未优化时）或 O((V + E) log V)（使用优先队列时）3. 应用：适用于无负权边的图。4. 核心思想(1) 选定一个点，这个点满足两个条件：a.未被选过，b.距离最短(2) 对于这个点的所有邻近点去尝试松弛

---

实现代码（未优化版本）

---

// 求最短路径
// Dijkstra 不断选择当前距离源节点最近的未处理节点来构建最短路径。
// 贪心算法
// 时间复杂度 O(V^2)
void MyGraph::Dijkstra(int startVertex)
{//代表某个顶点是否被访问过，初始化所有的顶点为 falsevector<bool> visited(n, false);//dis代表源点到其它点的最短距离，numeric_limits<int>::max()代表无穷vector<int> distances(n, numeric_limits<int>::max()); //向量 prev 用来存储路径的前驱节点，用于之后路径重建，初始化为 -1vector<int> prev(n, -1);源点到源点的距离为 0distances[startVertex] = 0;//为什么只要寻找n-1个点呢？因为当剩下一个点的时候，这个点已经没有需要松弛的邻接点了for (int i = 0; i < n - 1; i++){//进入循环之后，一开始不知道哪个是没有被访问过且距离源点最短的int now_minDistance = numeric_limits<int>::max();int now_minVertex = -1;//使用这个循环开始寻找没有被访问过且距离源点最短距离的点for (int j = 0; j < n; j++)if (!visited[j] && distances[j] < now_minDistance)now_minDistance = distances[j], now_minVertex = j;//标记当前节点已访问visited[now_minVertex] = true;//对这个距离源点最短距离的点的所有邻接点进行松弛for (const auto &pair : adjList[now_minVertex]){//  松弛操作（Relaxation）if (distances[now_minVertex] + pair.second < distances[pair.first]){distances[pair.first] = distances[now_minVertex] + pair.second, prev[pair.first] = now_minVertex;}}}for (int i = 0; i < n; i++)if (i != startVertex)cout << "vertex " << i << " distance from " << startVertex << " is " << distances[i] << endl;}

---

实现代码（优化版本）

---

算法原理：

利用了优先队列（通常是最小堆）将时间复杂度降低到 O((V + E) log V)。

---

void MyGraph::Dijkstra_withOptimize(int startVertex)
{vector<bool> visited(n, false);                       vector<int> distances(n, numeric_limits<int>::max()); vector<int> prev(n, -1);                              priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, startVertex});distances[startVertex] = 0; // for(int i = 0; i < n - 1; i++){while (!pq.empty()){// int now_minDistance = numeric_limits<int>::max();// int now_minVertex = -1;int now_minDistance = pq.top().first;int now_minVertex = pq.top().second;pq.pop();// for(int j = 0; j < n; j++) if(!visited[j] && distances[j] < now_minDistance) now_minDistance = distances[j], now_minVertex = j; //don't need amymorevisited[now_minVertex] = true;for (const auto &neighbor : adjList[now_minVertex]){// int neighborDistance = distances[now_minVertex] + neighbor.second;int neighborDistance = now_minDistance + neighbor.second;// if(neighborDistance < distances[neighbor.first]) distances[neighbor.first] = neighborDistance, prev[neighbor.first] = now_minVertex;if (neighborDistance < distances[neighbor.first]){distances[neighbor.first] = neighborDistance;prev[neighbor.first] = now_minVertex;pq.push({neighborDistance, neighbor.first});}}}for (int i = 0; i < n; i++)if (i != startVertex)cout << "vertex " << i << " distance from " << startVertex << " is " << distances[i] << endl;
}

---

2. Bellman-Ford 算法（单源最短路径）（负边权图）

---

算法原理

1. Bellman-Ford 算法 ——> 带负权边的图2. 时间复杂度是 (O(n \times E))，其中 (n) 是顶点数，(E) 是边数。3. Bellman-Ford算法的主要思想通过最多 (n - 1) 次松弛操作（Relaxation），逐步逼近最短路径。松弛操作会不断尝试更新路径，直到无法再优化路径为止。4. 如果图中存在负权回路（负权环）的情况，这种情况是求不出最短路径的！       但 Bellman-Ford 算法可以对负权回路的情况进行检测负权环检测：经过 V-1 次松弛操作后，如果还存在可以松弛的边，说明图中存在负权环

---

算法步骤

1.初始化：dist[start] = 0，其他所有节点的距离 dist[] = ∞2. 松弛操作：对每条边 (u, v) 进行 V-1 次松弛操作。如果 dist[u] + weight < dist[v]，则更新 dist[v]。3.负权环检测：对每一条边 (u, v) 进行一次松弛操作。如果有边 (u, v) 能够进一步放松，说明图中存在负权环需要注意的是，以 S 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

---

代码实现

void MyGraph::BellmanFord(int startVertex)
{// 1.初始化vector<int> distances(n, numeric_limits<int>::max());distances[startVertex] = 0;// 2. 松弛操作// 对每条边 (u, v) 进行 V-1 次松弛操作for (int i = 0; i < n - 1; i++)for (int j = 0; j < n; j++)for (const auto &pair : adjList[j])// 如果 dist[u] + weight < dist[v]，则更新 dist[v]if (distances[j] != numeric_limits<int>::max() && distances[j] + pair.second < distances[pair.first])distances[pair.first] = distances[j] + pair.second;// 3.负权环检测// 对每一条边 (u, v) 进行一次松弛操作。for (int j = 0; j < n; j++)for (const auto &pair : adjList[j])// 如果有边 (u, v) 能够进一步放松，说明图中存在负权环if (distances[j] != numeric_limits<int>::max() && distances[j] + pair.second < distances[pair.first]){cout << "Graph contains a negative weight cycle!" << endl;return;}//打印输出for (int i = 0; i < n; i++)if (i != startVertex)cout << "vertex " << i << " distance from " << startVertex << " is " << distances[i] << endl;cout << endl;
}

---

比较 Bellman-Ford 算法 和 Dijkstra 算法的工作机制

（1）关键区别：

1. Dijkstra 算法：贪心策略每次选择尚未处理的最小距离顶点，然后对其邻接顶点进行松弛操作。优先队列（通常是最小堆）优化2. Bellman-Ford 算法：动态规划算法对图中的每条边执行 n - 1 次松弛操作来计算从源节点到其他所有节点的最短路径。

（2）为什么 Bellman-Ford 不需要找最小值？

    a 遍历所有边的松弛操作：Bellman-Ford 通过对所有边进行遍历和松弛操作，它保证了在最多 n-1 轮迭代后，所有的最短路径都会被正确计算出来。n-1 轮的原因是：在最坏的情况下，最短路径最多需要经过 n-1 条边。b 负权边的处理：Dijkstra 无法处理负权边，而 Bellman-Ford 可以处理负权边。由于负权边的存在，单纯选择最小值无法保证最优解，因此 Bellman-Ford 不像 Dijkstra 那样依赖每步选择最小值顶点。

（3）为什么由于负权边的存在，Bellman-Ford 如果单纯选择最小值无法保证最优解？

---

2. Floyd-Warshall算法（多源最短路径）

算法原理：

1. 动态规划2. 所有顶点对之间的最短路径。3. 三重循环（引入中间节点，逐步优化路径）4. 时间复杂度为 O(n^3)5. 适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）

---

算法步骤

1. 初始化如果有一条边 (i, j)，则 dist[i][j] = w(i, j)，即边的权重。如果没有边，则 dist[i][j] = ∞。对于同一节点 i，初始化 dist[i][i] = 0，因为从一个节点到自身的距离为0。2. 迭代更新对于每一对节点 (i, j)，检查是否通过中间节点 k 可以得到更短的路径即判断是否 dist[i][j] > dist[i][k] + dist[k][j]如果是，则更新 dist[i][j] 为新的最短路径 dist[i][k] + dist[k][j]3. 终止条件：在经过 V 次迭代（每次迭代考虑一个新的中间节点 k）后，dist[i][j] 就是节点 i 到节点 j 的最短路径

---

实现代码

void MyGraph::FloydWarshall()
{// 1. 初始化// 创建一个二维向量 distances 用来存储两点之间的路径长度，初始化为顶点数量 n 大小，每个元素设置为无穷大（代表两点之间没有路径）vector<vector<int>> distances(n, vector<int>(n, numeric_limits<int>::max()));// 创建一个二维向量 prev 用来存储路径的前驱节点，用于之后路径重建，初始化为 -1vector<vector<int>> prev(n, vector<int>(n, -1));// 所有节点到自己的距离为 0，因此将 distances[i][i] 设为 0。for (int i = 0; i < n; i++)distances[i][i] = 0;// 初始化相邻节点之间的距离。遍历每个节点 i 的邻接表 adjList[i]，将边的权重 edge.second 设置为相应的 distances[i][edge.first]// 将 prev[i][edge.first] 设置为 i，表示 i 是 edge.first 的前驱。for (int i = 0; i < n; i++)for (const auto &edge : adjList[i])distances[i][edge.first] = edge.second, prev[i][edge.first] = i;// 2. 迭代更新// Floyd-Warshall 的核心！！！// 通过引入中间节点 k，检查从节点 i 经过 k 再到 j 的路径是否比 i 直接到 j 更短。如果是，则更新 distances[i][j] 和 prev[i][j]for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (distances[i][k] != numeric_limits<int>::max() && distances[k][j] != numeric_limits<int>::max() && distances[i][k] + distances[k][j] < distances[i][j])distances[i][j] = distances[i][k] + distances[k][j], prev[i][j] = prev[k][j];// 输出所有顶点对之间的最短路径for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (i != j)cout << "Vertex " << i << " to " << j << " distance is " << distances[i][j] << endl;
}

---