C语言实现最短路径算法
最短路径算法是图论中的经典问题，常见的算法包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等,下面我将分别介绍这三种算法的C语言实现。
（图片来源网络，侵删）
Dijkstra算法（单源最短路径）
Dijkstra算法用于计算从单个源点到所有其他顶点的最短路径,适用于非负权重的图。
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 9 // 顶点数量
// 找到未访问顶点中距离最小的顶点
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// 打印最短路径
void printSolution(int dist[]) {
printf("顶点\t距离\n");
for (int i = 0; i < V; i++) {
printf("%d\t%d\n", i, dist[i]);
}
}
// Dijkstra算法实现
void dijkstra(int graph[V][V], int src) {
int dist[V]; // 存储最短距离
bool sptSet[V]; // sptSet[i]为true表示顶点i在最短路径树中
// 初始化距离数组和sptSet数组
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}
// 源点到自身的距离为0
dist[src] = 0;
// 对所有顶点进行处理
for (int count = 0; count < V - 1; count++) {
// 选择未访问顶点中距离最小的顶点
int u = minDistance(dist, sptSet);
// 标记该顶点为已访问
sptSet[u] = true;
// 更新相邻顶点的距离
for (int v = 0; v < V; v++) {
// 更新条件：1.顶点v未被访问 2.存在边u-v 3.通过u到v的距离更短
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 打印结果
printSolution(dist);
}
int main() {
/* 示例图 */
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}
Bellman-Ford算法（处理负权重）
Bellman-Ford算法可以处理带有负权重的图,并能检测负权重环。
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5 // 顶点数量
#define E 8 // 边数量
// 结构体表示边
struct Edge {
int src, dest, weight;
};
// 打印结果
void printArr(int dist[], int n) {
printf("顶点\t距离\n");
for (int i = 0; i < n; ++i) {
printf("%d\t%d\n", i, dist[i]);
}
}
// Bellman-Ford算法实现
bool bellmanFord(struct Edge edges[], int E, int V, int src) {
int dist[V];
// 初始化距离数组
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
}
dist[src] = 0;
// 对所有边进行V-1次松弛
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// 检查负权重环
for (int i = 0; i < E; i++) {
int u = edges[i].src;
int v = edges[i].dest;
int weight = edges[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("图中存在负权重环\n");
return false;
}
}
printArr(dist, V);
return true;
}
int main() {
struct Edge edges[] = {
{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2},
{1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3}
};
int V = 5;
int E = sizeof(edges) / sizeof(edges[0]);
bellmanFord(edges, E, V, 0);
return 0;
}
Floyd-Warshall算法（所有顶点对最短路径）
Floyd-Warshall算法用于计算图中所有顶点对之间的最短路径。
#include <stdio.h>
#include <limits.h>
#define V 4 // 顶点数量
// 打印距离矩阵
void printSolution(int dist[][V]) {
printf("所有顶点对之间的最短距离:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INT_MAX) {
printf("INF\t");
} else {
printf("%d\t", dist[i][j]);
}
}
printf("\n");
}
}
// Floyd-Warshall算法实现
void floydWarshall(int graph[][V]) {
int dist[V][V];
// 初始化距离矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 对每个顶点作为中间顶点进行计算
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printSolution(dist);
}
int main() {
/* 示例图 */
int graph[V][V] = {
{0, 5, INT_MAX, 10},
{INT_MAX, 0, 3, INT_MAX},
{INT_MAX, INT_MAX, 0, 1},
{INT_MAX, INT_MAX, INT_MAX, 0}
};
floydWarshall(graph);
return 0;
}
算法选择建议
-
Dijkstra算法：
（图片来源网络，侵删）- 适用于非负权重的图
- 时间复杂度：O(V²) 或 O(E + V log V)（使用优先队列）
- 不能处理负权重
-
Bellman-Ford算法：
- 可以处理负权重
- 可以检测负权重环
- 时间复杂度：O(VE)
- 比Dijkstra慢，但适用范围更广
-
Floyd-Warshall算法：
- 计算所有顶点对之间的最短路径
- 时间复杂度：O(V³)
- 可以处理负权重（但不能有负权重环）
根据具体问题的需求选择合适的算法，如果只需要单源最短路径且权重非负，Dijkstra是最佳选择；如果可能存在负权重，使用Bellman-Ford；如果需要所有顶点对的最短路径，使用Floyd-Warshall。
（图片来源网络，侵删）
