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

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

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

Dijkstra算法：单源最短路径

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

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

示例代码：

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

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector> graph[MAXN]; // 邻接表：终点，权重
int dist[MAXN];
bool visited[MAXN];
void dijkstra(int start, int n) {
fill(dist, dist + n + 1, INF);
dist[start] = 0;
priority_queue, vector>, greater>> pq;
pq.push({0, start});
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 zuojiankuohaophpcn dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}
}
Floyd-Warshall算法：多源最短路径
可以求出图中任意两点之间的最短路径，适合小规模图或需要所有点对距离的情况。

							

								
								

									蓝心千询
									
蓝心千询是vivo推出的一个多功能AI智能助手
								
								下载 
							
						
基于动态规划，通过中间点逐步更新最短路径。

- 时间复杂度 O(V³)，空间复杂度 O(V²)
- 可处理负权边（但不能有负权环）
示例代码：
立即学习“C++免费学习笔记（深入）”；
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[500][500]; // dist[i][j] 表示 i 到 j 的最短距离
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]);
}
如何选择合适的方法？
根据实际问题选择：

- 只关心一个起点到其他点的距离 → 用 Dijkstra
- 需要知道任意两点间的最短路径 → 用 Floyd
- 图中有负权边但无负环 → 考虑 Bellman-Ford 或 SPFA（可自行实现）
- 点数少（如 ≤ 500）→ Floyd 更方便
- 点数多但边少 → Dijkstra + 邻接表更高效
基本上就这些。关键是理解算法适用条件，并正确建图和初始化距离数组。注意INF值不要设太大导致溢出，也不要太小影响判断。