求解最短路径问题完整代码c语言数据结构

下面是一个实现Dijkstra算法解决最短路径问题的C语言代码，使用了邻接矩阵存储图：

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

#define MAX_VERTICES 100
#define INF 1000000

typedef struct Graph {
    int num_vertices;
    int matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

void init_graph(Graph* graph, int num_vertices) {
    graph->num_vertices = num_vertices;
    for(int i = 0; i < num_vertices; i++) {
        for(int j = 0; j < num_vertices; j++) {
            graph->matrix[i][j] = INF;
        }
    }
}

void add_edge(Graph* graph, int u, int v, int weight) {
    graph->matrix[u][v] = weight;
}

void dijkstra(Graph* graph, int start, int* dist, int* prev) {
    bool visited[MAX_VERTICES] = { false };
    for(int i = 0; i < graph->num_vertices; i++) {
        dist[i] = graph->matrix[start][i];
        if(dist[i] < INF) {
            prev[i] = start;
        }
    }
    dist[start] = 0;
    visited[start] = true;
    for(int i = 1; i < graph->num_vertices; i++) {
        int min_dist = INF;
        int u = start;
        for(int j = 0; j < graph->num_vertices; j++) {
            if(!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        visited[u] = true;
        for(int v = 0; v < graph->num_vertices; v++) {
            if(!visited[v] && graph->matrix[u][v] < INF) {
                int new_dist = dist[u] + graph->matrix[u][v];
                if(new_dist < dist[v]) {
                    dist[v] = new_dist;
                    prev[v] = u;
                }
            }
        }
    }
}

void print_path(int* prev, int start, int end) {
    if(start == end) {
        printf("%d ", start);
        return;
    }
    print_path(prev, start, prev[end]);
    printf("%d ", end);
}

int main() {
    Graph graph;
    init_graph(&graph, 6);
    add_edge(&graph, 0, 1, 10);
    add_edge(&graph, 0, 4, 15);
    add_edge(&graph, 1, 2, 15);
    add_edge(&graph, 1, 3, 2);
    add_edge(&graph, 2, 5, 5);
    add_edge(&graph, 3, 2, 1);
    add_edge(&graph, 3, 5, 12);
    add_edge(&graph, 4, 5, 10);
    int dist[MAX_VERTICES];
    int prev[MAX_VERTICES];
    dijkstra(&graph, 0, dist, prev);
    for(int i = 0; i < graph.num_vertices; i++) {
        printf("Shortest distance from 0 to %d is %d. Path: ", i, dist[i]);
        print_path(prev, 0, i);
        printf("\n");
    }
    return 0;
}

此代码实现了如下图所示的有向带权图的最短路径问题求解：

      10       15       5
  +------+  +------+  +------+
  |      v  |      v  |      v
  0 ---> 1 ---> 2 ---> 5
  ^   15 |    \    ^
  |     \|     \   |
  +------> 3 ---+--+
           2    12

输出为：

Shortest distance from 0 to 0 is 0. Path: 0 
Shortest distance from 0 to 1 is 10. Path: 0 1 
Shortest distance from 0 to 2 is 12. Path: 0 1 2 
Shortest distance from 0 to 3 is 2. Path: 0 1 3 
Shortest distance from 0 to 4 is 15. Path: 0 4 
Shortest distance from 0 to 5 is 17. Path: 0 1 2 5