使用迪杰斯特拉算法求解最短路径的C语言代码示例

以下是一个使用迪杰斯特拉算法求解最短路径的C语言代码：

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100
#define INF 9999

typedef struct {
    int weight;
    int length;
} Edge;

typedef struct {
    int vertex;
    Edge edge[MAX_SIZE];
} Graph;

void dijkstra(Graph *graph, int source, int n) {
    int dist[MAX_SIZE];
    bool visited[MAX_SIZE];

    // 初始化距离和访问数组
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    // 设置源点的距离为0
    dist[source] = 0;

    for (int i = 0; i < n - 1; i++) {
        int minDist = INF;
        int minIndex = -1;

        // 找到当前未访问的距离最小的点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        // 标记该点为已访问
        visited[minIndex] = true;

        // 更新与该点相邻的点的距离
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIndex].edge[j].weight != INF) {
                int newDist = dist[minIndex] + graph[minIndex].edge[j].weight;
                if (newDist < dist[j]) {
                    dist[j] = newDist;
                }
            }
        }
    }

    // 输出最短路径
    printf("最短路径：\n");
    for (int i = 0; i < n; i++) {
        printf("源点 %d 到点 %d 的最短距离为 %d\n", source, i, dist[i]);
    }
}

int main() {
    int n;
    printf("请输入图的顶点数：");
    scanf("%d", &n);

    Graph graph[n];
    printf("请输入图的边信息：\n");
    for (int i = 0; i < n; i++) {
        graph[i].vertex = i;
        for (int j = 0; j < n; j++) {
            int weight;
            printf("请输入点 %d 到点 %d 的距离（若不可达请输入INF）：", i, j);
            scanf("%d", &weight);
            graph[i].edge[j].weight = weight;
        }
    }

    int source;
    printf("请输入源点：");
    scanf("%d", &source);

    dijkstra(graph, source, n);

    return 0;
}

要画出给定的带权有向图G，可以使用图形可视化工具如Graphviz来生成图形。

以下是一个使用Graphviz的dot语言代码示例：

digraph G {
    A -> B [label="2"];
    A -> C [label="4"];
    B -> C [label="1"];
    B -> D [label="7"];
    C -> D [label="3"];
    C -> E [label="5"];
    D -> E [label="2"];
}

将上述代码保存为.dot文件，然后使用Graphviz工具生成图形：

dot -Tpng graph.dot -o graph.png

这将生成一个名为graph.png的图形文件，表示给定的带权有向图G。