C语言迪杰斯特拉算法输出最短路径和权值

迪杰斯特拉算法可以用来求解加权有向图中的最短路径。其基本思想是，从起点开始，依次选择与起点距离最短的顶点，并更新与该顶点相邻的顶点的距离，直到到达终点或者所有顶点都被遍历。

使用C语言实现迪杰斯特拉算法，可以按照以下步骤进行：

1. 定义一个数组dist，用来记录每个顶点到起点的距离。初始化时，起点的距离为0，其余顶点的距离为无穷大。

2. 定义一个数组visited，用来记录每个顶点是否被遍历过。初始时，所有顶点都未被遍历过。

3. 从起点开始，依次选择与起点距离最短的顶点，并将该顶点标记为已遍历。

4. 遍历与该顶点相邻的顶点，并更新其距离。如果该顶点的距离比原来的距离更短，则更新该顶点的距离。

5. 重复步骤3和4，直到到达终点或者所有顶点都被遍历。

6. 最终，dist数组中存储的即为每个顶点到起点的最短距离。如果需要输出最短路径，可以记录每个顶点的前驱节点，然后倒序遍历即可。

下面是一个简单的迪杰斯特拉算法示例代码，以邻接矩阵表示图：

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int dist[MAX_VERTICES]; // 距离数组
int visited[MAX_VERTICES]; // 是否被遍历

int dijkstra(int start, int end, int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = (i == start ? 0 : INT_MAX);
        visited[i] = 0;
    }

    // 开始遍历
    for (int i = 0; i < n; i++) {
        // 找到距离起点最近的顶点
        int min_dist = INT_MAX;
        int min_vertex = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_vertex = j;
            }
        }
        if (min_vertex == -1) break; // 所有顶点已经被遍历

        visited[min_vertex] = 1; // 标记为已遍历

        // 更新与该顶点相邻的顶点的距离
        for (int j = 0; j < n; j++) {
            if (graph[min_vertex][j] != 0 && !visited[j]) {
                int new_dist = dist[min_vertex] + graph[min_vertex][j];
                if (new_dist < dist[j]) {
                    dist[j] = new_dist;
                }
            }
        }
    }

    return dist[end]; // 返回终点到起点的最短距离
}

int main() {
    int n, m; // n为顶点数，m为边数
    scanf("%d%d", &n, &m);

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    // 读入边信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = w;
    }

    // 执行迪杰斯特拉算法
    int start = 0, end = n - 1;
    int shortest_dist = dijkstra(start, end, n);

    // 输出最短距离
    printf("%d\n", shortest_dist);

    return 0;
}

注意：上述代码中的邻接矩阵表示法只适用于稠密图，对于稀疏图可以使用邻接表等数据结构来表示。同时，如果存在负权边，那么迪杰斯特拉算法就不再适用，需要使用其他算法。