c++中如何求图的最短路径_c++图最短路径计算方法-C++-PHP中文网

c++中如何求图的最短路径_c++图最短路径计算方法

尼克

发布： 2025-10-11 18:14:01

原创

342人浏览过

Dijkstra算法用于单源最短路径，适合非负权边的稀疏图，时间复杂度O((V+E)logV)；Floyd-Warshall算法求多源最短路径，适用于小规模图，可处理负权边但不能有负环，时间复杂度O(V³)。

c++中如何求图的最短路径_c++图最短路径计算方法

在C++中求图的最短路径，常用的方法有Dijkstra算法和Floyd-Warshall算法，分别适用于不同场景。下面介绍这两种方法的基本原理和实现方式。

Dijkstra算法：单源最短路径

用于计算一个起点到图中其他所有顶点的最短路径，适用于非负权边的图。

核心思想是贪心策略，每次选择距离起点最近且未访问的节点进行扩展。

- 使用优先队列（堆）优化，时间复杂度为 O((V + E) log V) - 适合稀疏图

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <bits/stdc++.h>
using namespace std;
<p>const int INF = 0x3f3f3f3f;
const int MAXN = 1005;</p><p>vector<pair<int, int>> graph[MAXN]; // 邻接表：终点，权重
int dist[MAXN];
bool visited[MAXN];</p><p>void dijkstra(int start, int n) {
fill(dist, dist + n + 1, INF);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});</p><pre class='brush:php;toolbar:false;'>while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (visited[u]) continue;
    visited[u] = true;

    for (auto &edge : graph[u]) {
        int v = edge.first;
        int w = edge.second;
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

登录后复制

}

Floyd-Warshall算法：多源最短路径

可以求出图中任意两点之间的最短路径，适合小规模图或需要所有点对距离的情况。

图酷AI

下载即用！可以免费使用的AI图像处理工具，致力于为用户提供最先进的AI图像处理技术，让图像编辑变得简单高效。

查看详情

基于动态规划，通过中间点逐步更新最短路径。

- 时间复杂度 O(V³)，空间复杂度 O(V²) - 可处理负权边（但不能有负权环）

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <bits/stdc++.h>
using namespace std;
<p>const int INF = 0x3f3f3f3f;
int dist[500][500]; // dist[i][j] 表示 i 到 j 的最短距离</p><p>void floyd(int n) {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}</p>

登录后复制

如何选择合适的方法？

根据实际问题选择：

- 只关心一个起点到其他点的距离 → 用 Dijkstra - 需要知道任意两点间的最短路径 → 用 Floyd - 图中有负权边但无负环 → 考虑 Bellman-Ford 或 SPFA（可自行实现） - 点数少（如 ≤ 500）→ Floyd 更方便 - 点数多但边少 → Dijkstra + 邻接表更高效

基本上就这些。关键是理解算法适用条件，并正确建图和初始化距离数组。注意INF值不要设太大导致溢出，也不要太小影响判断。

以上就是c++++中如何求图的最短路径_c++图最短路径计算方法的详细内容，更多请关注php中文网其它相关文章！