当前位置： 首页 > news >正文

C语言最短路径

news 2026/5/10 22:06:20

C语言最短路径

C语言最短路径（BFS/DFS/Dijkstra/Floyd）

目录
  • C语言最短路径（BFS/DFS/Dijkstra/Floyd）
    • 一、算法前置知识
      • 1.1 核心概念
    • 二、BFS 广度优先搜索（无权图最短路径）
      • 2.1 算法原理
      • 2.2 适用场景
      • 2.3 C语言完整实现
      • 2.4 核心特点
    • 三、DFS 深度优先搜索（暴力枚举路径）
      • 3.1 算法原理
      • 3.2 适用场景
      • 3.3 C语言完整实现
      • 3.4 核心特点
    • 四、Dijkstra 迪杰斯特拉算法（非负权单源最短路）
      • 4.1 算法原理
      • 4.2 适用场景
      • 4.3 朴素版 C语言完整实现
      • 4.4 核心特点
    • 五、Floyd 弗洛伊德算法（多源最短路）
      • 5.1 算法原理
      • 5.2 适用场景
      • 5.3 C语言完整实现
      • 5.4 核心特点
    • 六、四大算法全方位对比总结

前言

日常场景中的地图导航、路线规划、网络路径择优，本质都是求解图的最短路径。

本文主讲关于四大主流最短路径算法：

  1. BFS广度优先搜索：无权图专属最短路径

  2. DFS深度优先搜索：暴力枚举所有路径，适配小规模图

  3. Dijkstra迪杰斯特拉：非负权图单源最短路径最优解

  4. Floyd弗洛伊德：多源最短路径万能暴力算法

一、算法前置知识

1.1 核心概念

• 无权图：所有边的权重为1（如迷宫格子、普通连通节点）

• 有权图：边带有数值权重（距离、耗时、费用，可正可负）

• 单源最短路径：一个起点到所有终点的最短路径

• 多源最短路径：任意两点之间的最短路径

二、BFS 广度优先搜索（无权图最短路径）

2.1 算法原理

BFS是无权图最短路径的最优解法，核心思想：逐层遍历、先到即最短。

从起点出发，一层一层向外扩散遍历节点，因为所有边权重相等，第一次访问到目标节点的路径，一定是最短路径。底层依赖队列先进先出特性实现。

2.2 适用场景

• 仅适用于无权无向/有向图

• 迷宫最短步数、最少换乘、最少操作次数等场景

2.3 C语言完整实现


#include <stdio.h>
#include <string.h>#define MAXN 100005   // 最大节点数
#define MAXM 200005   // 最大边数（无向图需开两倍）// 邻接表所需数组
int head[MAXN];      // head[u] 存储结点 u 的第一条边的编号
int to[MAXM];        // to[i] 存储第 i 条边的终点
int nxt[MAXM];       // nxt[i] 存储下一条边的编号
int edge_cnt;        // 边的计数器// 添加一条有向边 u -> v
void add_edge(int u, int v) {to[edge_cnt] = v;nxt[edge_cnt] = head[u];head[u] = edge_cnt++;
}// BFS：从源点 s 出发，计算到各点的最短距离（无权）
// 参数：s - 源点编号，dist - 距离数组（需外部定义），n - 节点总数
void bfs(int s, int dist[], int n) {int queue[MAXN];     // 数组模拟队列int front = 0, rear = 0;// 初始化距离为 -1 表示未访问for (int i = 0; i < n; i++) dist[i] = -1;dist[s] = 0;queue[rear++] = s;while (front < rear) {int u = queue[front++];for (int e = head[u]; e != -1; e = nxt[e]) {int v = to[e];if (dist[v] == -1) {          // 第一次访问即为最短距离dist[v] = dist[u] + 1;queue[rear++] = v;}}}
}int main() {// 初始化邻接表：所有头指针置为 -1memset(head, -1, sizeof(head));edge_cnt = 0;int n, m;scanf("%d %d", &n, &m);              // n 个点，m 条边for (int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);add_edge(u, v);                  // 有向图// add_edge(v, u);               // 若为无向图，加上这行}int dist[MAXN];bfs(0, dist, n);                     // 假设源点为 0for (int i = 0; i < n; i++) {printf("dist[%d] = %d\n", i, dist[i]);}return 0;
}

2.4 核心特点

  • 无权图必最优、效率最高
  • 无法处理带权重的路径问题

三、DFS 深度优先搜索（暴力枚举路径）

3.1 算法原理

DFS采用一路走到底、回溯枚举的思想，通过递归遍历图中所有可达路径，记录所有路径长度，最终筛选出最小值。

DFS没有最短路径的贪心特性，只是暴力枚举所有可能路径，因此仅适合小规模图。

3.2 适用场景

  • 节点数量极少的无权/有权图
  • 需要枚举所有路径的场景（非最优首选）

3.3 C语言完整实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>#define MAXN 100005   // 最大节点数
#define MAXM 200005   // 最大边数（无向图需开两倍）// ---------- 邻接表 ----------
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
void add_edge(int u, int v) {to[edge_cnt] = v;nxt[edge_cnt] = head[u];head[u] = edge_cnt++;
}// ---------- 递归 DFS ----------
// 参数: u - 当前节点, vis - 访问标记数组
void dfs_recursive(int u, bool vis[]) {vis[u] = true;printf("%d ", u);   // 访问节点（可替换为其他操作）for (int e = head[u]; e != -1; e = nxt[e]) {int v = to[e];if (!vis[v]) {dfs_recursive(v, vis);}}
}// ---------- 迭代 DFS（显式栈，防递归栈溢出）----------
// 需要手动模拟栈，栈中元素可携带额外状态（例如当前边遍历进度）
// 下面给出最简版本（仅存储节点，但遍历顺序与递归略有差异，仍是 DFS）
#include <stdlib.h>void dfs_iterative(int start, bool vis[]) {int stack[MAXN];int top = 0;stack[top++] = start;while (top > 0) {int u = stack[--top];if (vis[u]) continue;   // 防止重复入栈（有的写法会重复）vis[u] = true;printf("%d ", u);// 注意：为了保持与递归顺序相近，可逆序入栈或任意顺序for (int e = head[u]; e != -1; e = nxt[e]) {int v = to[e];if (!vis[v]) {stack[top++] = v;}}}
}// 如果需要精确模拟递归（例如处理回溯时的额外操作），可存储 (u, next_edge_index)
// 这里给出一个更通用的栈帧版本（可选，按需使用）
typedef struct {int node;int edge_idx;   // 当前已遍历的边在邻接表中的指针（实际存边编号）
} StackFrame;void dfs_iterative_adv(int start, bool vis[]) {StackFrame stack[MAXN];int top = 0;stack[top++] = (StackFrame){start, head[start]};vis[start] = true;printf("%d ", start);while (top > 0) {StackFrame *cur = &stack[top-1];if (cur->edge_idx == -1) {// 所有邻边处理完毕，回溯top--;continue;}int v = to[cur->edge_idx];cur->edge_idx = nxt[cur->edge_idx];   // 移到下一条边if (!vis[v]) {vis[v] = true;printf("%d ", v);stack[top++] = (StackFrame){v, head[v]};}}
}int main() {memset(head, -1, sizeof(head));edge_cnt = 0;int n, m;scanf("%d %d", &n, &m);for (int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);add_edge(u, v);// add_edge(v, u);   // 无向图请取消注释}bool vis[MAXN] = {false};// 调用递归 DFS（注意：图可能不连通，需要循环所有节点）printf("Recursive DFS: ");for (int i = 0; i < n; i++) {if (!vis[i]) dfs_recursive(i, vis);}printf("\n");// 重置访问标记memset(vis, 0, sizeof(vis));printf("Iterative DFS (simple stack): ");for (int i = 0; i < n; i++) {if (!vis[i]) dfs_iterative(i, vis);}printf("\n");return 0;
}

3.4 核心特点

• 暴力枚举，大数据量必超时

• 仅作为遍历工具，不推荐用于正规最短路径求解

四、Dijkstra 迪杰斯特拉算法（非负权单源最短路）

4.1 算法原理

贪心思想核心：每次从未确定最短路径的节点中，选出距离起点最近的节点，标记为已确定，再用该节点更新其他节点的距离，迭代直至所有节点遍历完成。

4.2 适用场景

• 带非负权重的有向/无向图

• 单源最短路径工业级最优解

4.3 朴素版 C语言完整实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>#define MAXN 1005
#define INF 0x3f3f3f3fint graph[MAXN][MAXN];   // 邻接矩阵，初始化为 INF
int dist[MAXN];
bool visited[MAXN];void dijkstra(int n, int start) {// 初始化memset(dist, 0x3f, sizeof(dist));memset(visited, 0, sizeof(visited));dist[start] = 0;for (int i = 0; i < n; i++) {// 找到未访问中距离最小的点int u = -1, min_dist = INF;for (int j = 0; j < n; j++) {if (!visited[j] && dist[j] < min_dist) {min_dist = dist[j];u = j;}}if (u == -1) break;   // 不连通visited[u] = true;// 松弛相邻节点for (int v = 0; v < n; v++) {if (!visited[v] && graph[u][v] != INF) {if (dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}}
}int main() {int n, m, start;scanf("%d %d %d", &n, &m, &start);// 初始化邻接矩阵memset(graph, 0x3f, sizeof(graph));for (int i = 0; i < m; i++) {int u, v, w;scanf("%d %d %d", &u, &v, &w);// 若有重边，取最小值if (w < graph[u][v]) graph[u][v] = w;// 无向图则加 graph[v][u] = w;}dijkstra(n, start);for (int i = 0; i < n; i++) {printf("dist[%d] = %d\n", i, dist[i] == INF ? -1 : dist[i]);}return 0;
}

4.4 核心特点

• 不能处理负权边，负权会破坏贪心正确性

• 单源最短路首选算法，效率远高于Floyd

五、Floyd 弗洛伊德算法（多源最短路）

5.1 算法原理

基于动态规划思想，核心公式：

mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j])

含义：i到j的最短路径 = 直接i→j 或 i→k→j 的最小值，枚举所有中间节点k，松弛所有两点间路径。

一次遍历即可求出任意两点之间的最短路径，是最简单的多源最短路算法。

5.2 适用场景

• 节点数较少（≤100）的有权图

• 需要批量查询任意两点最短路径

• 可处理负权边（不可处理负权环）

5.3 C语言完整实现

#include <stdio.h>
#include <string.h>#define MAXN 505        // 最大节点数（根据题目调整）
#define INF 0x3f3f3f3f  // 表示无穷大int dist[MAXN][MAXN];   // 距离矩阵，初始为 INF，对角线为 0// 初始化距离矩阵
void init(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = (i == j) ? 0 : INF;}}
}// 添加一条有向边 u->v，权值为 w
void add_edge(int u, int v, int w) {if (w < dist[u][v]) {   // 处理重边，取最小值dist[u][v] = w;}// 若无向图则再添加 dist[v][u] = w;
}// Floyd-Warshall 主过程
void floyd(int n) {for (int k = 0; k < n; k++) {          // 中间点for (int i = 0; i < n; i++) {      // 起点if (dist[i][k] == INF) continue; // 小优化：跳过不可能的情况for (int j = 0; j < n; j++) {  // 终点if (dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}
}// 检测负环（可选）：若存在 dist[i][i] < 0 则有负环
int has_negative_cycle(int n) {for (int i = 0; i < n; i++) {if (dist[i][i] < 0) return 1;}return 0;
}int main() {int n, m;scanf("%d %d", &n, &m);init(n);                     // 初始化距离矩阵for (int i = 0; i < m; i++) {int u, v, w;scanf("%d %d %d", &u, &v, &w);// 若节点编号从 1 开始，需转换为 0 基 : u--, v--;add_edge(u, v, w);// add_edge(v, u, w);    // 无向图加上此行}floyd(n);// 输出所有点对的最短距离for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][j] == INF)printf("INF ");elseprintf("%d ", dist[i][j]);}printf("\n");}// 若需要检测负环if (has_negative_cycle(n)) {printf("存在负环\n");}return 0;
}

5.4 核心特点

• 代码极简，三行核心循环搞定多源最短路

• 效率低，节点多（>100）直接超时

• 支持负权边，不支持负权环

六、四大算法全方位对比总结

算法 核心思想 使用场景 优缺点
BFS 层次遍历 无权图单源最短路 效率最高、仅限无权图
DFS 回溯枚举 极小图路径枚举 暴力低效、不推荐最短路使用
Dijkstra 贪心择优 非负权图单源最短路 单源最优、不支持负权
Floyd 动态规划 小规模图多源最短路线 代码极简、支持负权、效率低