c语言编程有向图的最短路径

要实现有向图的最短路径算法，可以使用 Dijkstra 算法或者 Bellman-Ford 算法。下面分别介绍这两种算法的实现方法。

1. Dijkstra 算法

Dijkstra 算法是一种贪心算法，用于求解带权有向图中单源最短路径问题。算法的基本思路是，维护一个集合 S 和一个距离数组 dist，初始时集合 S 中只包含源点，dist 中除源点外所有节点的距离都为无穷大。每次从 dist 中选取距离最小的节点 u，并将 u 加入集合 S 中，然后更新 u 的邻居节点的距离。重复执行这个过程，直到所有节点都被加入集合 S 中。

以下是 Dijkstra 算法的 C 语言实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000
#define INF INT_MAX

int n, m;  // n 表示节点数，m 表示边数
int g[MAXN][MAXN];  // 存储图的邻接矩阵
int dist[MAXN];  // 存储距离数组
int visited[MAXN];  // 记录节点是否被访问过

void dijkstra(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && g[u][v] != INF && dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = w;  // 存储边权
    }
    int s;
    scanf("%d", &s);  // 输入源点
    dijkstra(s);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    return 0;
}

2. Bellman-Ford 算法

Bellman-Ford 算法是一种动态规划算法，用于求解带权有向图中单源最短路径问题。算法的基本思路是，从源点开始进行 n-1 轮松弛操作，每轮松弛操作将所有边进行一次松弛，即尝试通过一条边缩短到达一个节点的距离。若在第 n 轮松弛操作后仍然存在可松弛的边，则说明图中存在负环，即存在一个环，使得沿着这个环的方向遍历会使得距离越来越小。因此，Bellman-Ford 算法也可以用于检测负环。

以下是 Bellman-Ford 算法的 C 语言实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000
#define INF INT_MAX

int n, m;  // n 表示节点数，m 表示边数
int u[MAXN], v[MAXN], w[MAXN];  // 存储边的起点、终点和权重
int dist[MAXN];  // 存储距离数组

void bellman_ford(int s) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (dist[u[j]] != INF && dist[u[j]] + w[j] < dist[v[j]]) {
                dist[v[j]] = dist[u[j]] + w[j];
            }
        }
    }
    for (int j = 0; j < m; j++) {
        if (dist[u[j]] != INF && dist[u[j]] + w[j] < dist[v[j]]) {
            printf("Graph contains negative-weight cycle\n");
            return;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
    }
    int s;
    scanf("%d", &s);  // 输入源点
    bellman_ford(s);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    return 0;
}