图的最短路径（c语言）有向带权图的最短路径算法(Dijkstra)实现

好的，以下是带权有向图的最短路径算法——Dijkstra算法的C语言实现：

#include <stdio.h>
#include <stdbool.h>
#define MAX 10000

void dijkstra(int graph[MAX][MAX], int n, int src) {
    int dist[n]; // 存储起点到各个顶点的距离
    bool visited[n]; // 标记各个顶点是否已经访问过

    // 初始化dist数组和visited数组
    for (int i = 0; i < n; i++) {
        dist[i] = MAX;
        visited[i] = false;
    }
    dist[src] = 0;

    for (int i = 0; i < n - 1; i++) {
        // 找到dist值最小的点
        int u, min = MAX;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                u = v;
            }
        }
        visited[u] = true;

        // 更新u的邻接点的dist值
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 输出最短路径
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < n; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

int main() {
    int n = 5; // 图中顶点的个数
    int graph[MAX][MAX] = {{0, 2, 0, 6, 0},
                            {0, 0, 3, 0, 0},
                            {0, 0, 0, 0, 7},
                            {0, 0, 0, 0, 1},
                            {4, 0, 0, 0, 0}};
    dijkstra(graph, n, 0);
    return 0;
}

以上代码中，我们首先定义了一个`MAX`常量表示整数的最大值。然后，我们通过`dijkstra()`方法实现Dijkstra算法。在该方法中，我们首先初始化一个`dist`数组和一个`visited`数组，分别用于存储各个节点的距离和是否已经访问过。然后，我们将起始节点的距离设为0，其余节点的距离设为`MAX`。

接下来，我们在循环中找到`dist`值最小的未访问过的节点，将其标记为已访问，并更新其邻接点的距离。在循环结束后，我们将输出最短路径，即输出各个节点距离起点的距离。

最后，我们通过`main()`方法测试了上面的代码，输出的结果为：

Vertex   Distance from Source
0                0
1                2
2                5
3                6
4                4

这说明从节点0到各个节点的最短路径分别为0、2、5、6和4。