用C语言写一个解决多段图的最短路径程序

在C语言中，我们可以使用Dijkstra算法来解决多段图（也称为带权无向图或多边形图）的最短路径问题。下面是一个简单的Dijkstra算法的实现，使用邻接矩阵表示图：

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

#define V 9 // 定义图的顶点数

// 边结构体
typedef struct Edge {
    int src, dest, weight;
} Edge;

// Dijkstra 算法函数
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 存储每个节点到源节点的距离
    bool visited[V] = {false}; // 标记节点是否已访问
    int i, u;

    // 初始化距离数组为无穷大，除了源节点
    for (i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (u = 0; u < V - 1; ) {
        // 找到未访问并且离源最近的节点
        i = minDistance(dist, visited);

        if (visited[i])
            u++;
        else {
            visited[i] = true;

            // 更新邻居节点的距离
            for (Edge edge : edges[i]) {
                int new_dist = dist[i] + edge.weight;
                if (new_dist < dist[edge.dest])
                    dist[edge.dest] = new_dist;
            }
        }
    }

    printf("Vertex \t\t Distance from Source\n");
    for (i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// 辅助函数，返回最小距离索引
int minDistance(int dist[], bool visited[]) {
    int min_index = -1;
    int min_value = INT_MAX;

    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] <= min_value)
            min_index = v, min_value = dist[v];
    }
    return min_index;
}

// 主函数，读入图的信息并调用Dijkstra算法
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;
}