C语言图论：最短路径算法

本文献给：
已掌握无向图基础，希望理解如何在带权图中找到两点间最短路径的C语言学习者。本文将系统讲解两种经典的最短路径算法。

你将学到：

1. 最短路径问题的定义与核心概念
2. Dijkstra算法：解决单源、非负权图的最短路径
3. Bellman-Ford算法：处理单源、含负权边的最短路径
4. 算法对比与实战应用

第一部分：问题定义与核心概念

1. 什么是最短路径？

在带权无向图G = ( V , E , w ) G = (V, E, w)G=(V,E,w)中，w : E → R w: E \rightarrow \mathbb{R}w:E→R为边权函数。从源点s ss到目标t tt的路径P = ( s , v 1 , . . . , v k , t ) P = (s, v_1, ..., v_k, t)P=(s,v1​,...,vk​,t)的长度为路径上所有边权之和：
d i s t ( P ) = ∑ i = 0 k w ( v i , v i + 1 ) dist(P) = \sum_{i=0}^{k} w(v_i, v_{i+1})dist(P)=i=0∑k​w(vi​,vi+1​)
最短路径是所有s ss到t tt路径中长度最小的路径。

关键术语：

• 单源最短路径：求从一个源点s ss到图中所有其他顶点的最短距离。
• 权值：可正、可负（实际问题中常为非负，如距离、时间、成本）。
• 松弛操作：最短路径算法的核心操作，通过考察一条边来更新当前的最短距离估计。

第二部分：图的存储（带权图）

在基础邻接矩阵/邻接表上，需要增加权值信息。

#defineMAX_V100#defineINF0x3f3f3f3f// 表示“无穷大”的一个较大数值// 邻接矩阵（带权）typedefstruct{intmatrix[MAX_V][MAX_V];// 存储权值，INF表示无边intvertex_count;}GraphMatrixWeighted;voidinit_graph_weighted(GraphMatrixWeighted*g,intn){g->vertex_count=n;for(inti=0;i<n;i++){for(intj=0;j<n;j++){g->matrix[i][j]=(i==j)?0:INF;// 自身距离为0}}}voidadd_edge_weighted(GraphMatrixWeighted*g,intu,intv,intweight){if(u>=g->vertex_count||v>=g->vertex_count)return;g->matrix[u][v]=weight;g->matrix[v][u]=weight;// 无向图}

第三部分：Dijkstra算法

1. 核心思想

贪心策略。维护一个集合S SS，包含已确定最短距离的顶点。每次从未确定的顶点中选择距离源点s ss最近的顶点u uu加入S SS，并用u uu来松弛其所有邻居的距离。要求：所有边权非负。

算法正确性依赖：当边权非负时，当前未确定顶点中距离最小的顶点，其距离不可能再被其他未确定的顶点更新减小。

2. 算法步骤（朴素O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)实现）

1. 初始化：dist[s] = 0，dist[v] = INF（v ≠ s），visited[v] = false。
2. 循环|V|次：
   a. 找到未访问顶点中dist最小的顶点u。
   b. 标记u为已访问 (visited[u] = true)。
   c.松弛操作：对u的每个邻居v，如果dist[u] + w(u, v) < dist[v]，则更新dist[v] = dist[u] + w(u, v)。
3. 循环结束，dist[]数组即为源点到各点的最短距离。

3. C语言实现

// Dijkstra算法 (邻接矩阵，朴素实现)voiddijkstra(GraphMatrixWeighted*g,intsrc,intdist[]){intvisited[MAX_V]={0};// 初始化for(inti=0;i<g->vertex_count;i++){dist[i]=INF;}dist[src]=0;for(intcount=0;count<g->vertex_count;count++){// 步骤1: 找到未访问的dist最小顶点intu=-1;intmin_dist=INF;for(intv=0;v<g->vertex_count;v++){if(!visited[v]&&dist[v]<min_dist){min_dist=dist[v];u=v;}}if(u==-1)break;// 剩余顶点不可达visited[u]=1;// 步骤2: 松弛u的所有邻居for(intv=0;v<g->vertex_count;v++){if(!visited[v]&&g->matrix[u][v]!=INF){intnew_dist=dist[u]+g->matrix[u][v];if(new_dist<dist[v]){dist[v]=new_dist;}}}}}

算法复杂度：

• 时间复杂度：O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)，适合稠密图。
• 空间复杂度：O ( ∣ V ∣ ) O(|V|)O(∣V∣)。
• 优化方向：使用**优先队列（最小堆）**可将时间复杂度降为O ( ( ∣ V ∣ + ∣ E ∣ ) log ⁡ ∣ V ∣ ) O((|V|+|E|) \log |V|)O((∣V∣+∣E∣)log∣V∣)，适合稀疏图。

第四部分：Bellman-Ford算法

1. 核心思想

动态规划/松弛。通过对所有边进行∣ V ∣ − 1 |V|-1∣V∣−1轮松弛操作，逐步逼近最短路径。可以处理负权边，并能检测出图中是否存在从源点可达的负权环。

原理：在无负权环的图中，任意两点间的最短路径最多包含∣ V ∣ − 1 |V|-1∣V∣−1条边。因此通过∣ V ∣ − 1 |V|-1∣V∣−1轮全局松弛足以找到所有最短路径。

2. 算法步骤

1. 初始化：dist[s] = 0，dist[v] = INF（v ≠ s）。
2. 进行∣ V ∣ − 1 |V|-1∣V∣−1轮迭代，每轮：
   • 遍历图中的所有边( u , v ) (u, v)(u,v)。
   • 对每条边执行松弛操作：如果dist[u] + w(u, v) < dist[v]，则更新dist[v] = dist[u] + w(u, v)。
3. 负权环检测：再进行一轮所有边的遍历。如果仍有边能被松弛，则说明图中存在从源点可达的负权环，最短路径无意义。

3. C语言实现

// Bellman-Ford算法 (使用边列表存储图更合适，此处为演示使用邻接矩阵遍历所有边)voidbellman_ford(GraphMatrixWeighted*g,intsrc,intdist[]){// 初始化for(inti=0;i<g->vertex_count;i++){dist[i]=INF;}dist[src]=0;// 步骤1: 进行 |V|-1 轮松弛for(inti=0;i<g->vertex_count-1;i++){// 遍历所有边 (u, v)for(intu=0;u<g->vertex_count;u++){for(intv=0;v<g->vertex_count;v++){if(g->matrix[u][v]!=INF){// 存在边intnew_dist=dist[u]+g->matrix[u][v];if(new_dist<dist[v]){dist[v]=new_dist;}}}}}// 步骤2: 检测负权环 (可选，如果需要检测)for(intu=0;u<g->vertex_count;u++){for(intv=0;v<g->vertex_count;v++){if(g->matrix[u][v]!=INF&&dist[u]+g->matrix[u][v]<dist[v]){printf("图中存在从源点可达的负权环！\n");return;}}}}

算法复杂度：

• 时间复杂度：O ( ∣ V ∣ ⋅ ∣ E ∣ ) O(|V| \cdot |E|)O(∣V∣⋅∣E∣)，使用邻接矩阵为O ( ∣ V ∣ 3 ) O(|V|^3)O(∣V∣3)，使用边列表为O ( ∣ V ∣ ⋅ ∣ E ∣ ) O(|V| \cdot |E|)O(∣V∣⋅∣E∣)。
• 空间复杂度：O ( ∣ V ∣ ) O(|V|)O(∣V∣)。

第五部分：总结与对比

算法对比表

选择指南

1. 绝大多数情况（边权非负）：优先使用Dijkstra算法（尤其是堆优化版本）。例如：道路导航、网络路由。
2. 图含有负权边：必须使用Bellman-Ford算法。例如：金融套利模型、某些特殊约束问题。
3. 需要检测负权环：使用 Bellman-Ford 算法。

觉得文章有帮助？别忘了：

👍 点赞 👍- 给我一点鼓励
⭐ 收藏 ⭐- 方便以后查看
🔔 关注 🔔- 获取更新通知

标签：#C语言#图论#最短路径#Dijkstra#Bellman-Ford#算法