C语言实现Dijkstra最短路径算法实验报告

实验题目：利用图的数据结构实现最短路径算法

实验目的

通过学习和实现图的数据结构，加深对图的概念和算法的理解，熟悉C语言的编程方法，掌握最短路径算法的原理和实现方法。

实验原理

最短路径算法是图论中的经典问题，它的目的是在图中找到两个点之间的最短路径。常用的算法有Dijkstra算法和Floyd算法。本次实验我们将实现Dijkstra算法。

Dijkstra算法的基本思路是从起点开始遍历图中的每个点，并记录到达每个点时的距离，直到找到终点为止。在遍历过程中，需要维护一个最短路径集合，用于保存已经找到的最短路径。同时，需要使用一个优先队列来保存当前可达点，以便在每次遍历时选择距离最短的点继续遍历。

实验步骤

定义图的结构体和边的结构体

#define MAX_VERTEX_NUM 20
#define MAX_EDGE_NUM 100

typedef struct {
    char vertex[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num, edge_num;
} Graph;

typedef struct {
    int start;
    int end;
    int weight;
} Edge;

初始化图

void init_graph(Graph *graph) {
    graph->vertex_num = 0;
    graph->edge_num = 0;
    int i, j;
    for(i = 0; i < MAX_VERTEX_NUM; i++) {
        for(j = 0; j < MAX_VERTEX_NUM; j++) {
            if(i == j) {
                graph->edge[i][j] = 0;
            }else {
                graph->edge[i][j] = INT_MAX;
            }
        }
    }
}

添加边

void add_edge(Graph *graph, char start, char end, int weight) {
    int i, j;
    for(i = 0; i < graph->vertex_num; i++) {
        if(graph->vertex[i] == start) {
            break;
        }
    }
    for(j = 0; j < graph->vertex_num; j++) {
        if(graph->vertex[j] == end) {
            break;
        }
    }
    if(i == graph->vertex_num) {
        graph->vertex[i] = start;
        graph->vertex_num++;
    }
    if(j == graph->vertex_num) {
        graph->vertex[j] = end;
        graph->vertex_num++;
    }
    graph->edge[i][j] = weight;
    graph->edge_num++;
}

实现Dijkstra算法

void dijkstra(Graph *graph, int start, int *dist, int *prev) {
    int visited[MAX_VERTEX_NUM] = {0};
    int i, j, k, min;
    for(i = 0; i < graph->vertex_num; i++) {
        dist[i] = graph->edge[start][i];
        visited[i] = 0;
        if(dist[i] == INT_MAX) {
            prev[i] = -1;
        }else {
            prev[i] = start;
        }
    }
    visited[start] = 1;
    for(i = 1; i < graph->vertex_num; i++) {
        min = INT_MAX;
        for(j = 0; j < graph->vertex_num; j++) {
            if(!visited[j] && dist[j] < min) {
                k = j;
                min = dist[j];
            }
        }
        visited[k] = 1;
        for(j = 0; j < graph->vertex_num; j++) {
            if(!visited[j] && dist[k] + graph->edge[k][j] < dist[j]) {
                dist[j] = dist[k] + graph->edge[k][j];
                prev[j] = k;
            }
        }
    }
}

输出结果

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

void output_result(Graph *graph, int *dist, int *prev) {
    int i, j;
    for(i = 0; i < graph->vertex_num; i++) {
        printf('%c ', graph->vertex[i]);
        if(dist[i] == INT_MAX) {
            printf("INF ");
        }else {
            printf('%d ', dist[i]);
        }
        if(prev[i] == -1) {
            printf("-
");
        }else {
            output_path(prev, 0, i);
            printf("
");
        }
    }
}

主函数调用

int main() {
    Graph graph;
    init_graph(&graph);
    add_edge(&graph, 'A', 'B', 10);
    add_edge(&graph, 'A', 'C', 3);
    add_edge(&graph, 'A', 'D', 20);
    add_edge(&graph, 'B', 'D', 5);
    add_edge(&graph, 'C', 'B', 2);
    add_edge(&graph, 'C', 'E', 15);
    add_edge(&graph, 'D', 'E', 11);
    int dist[MAX_VERTEX_NUM];
    int prev[MAX_VERTEX_NUM];
    dijkstra(&graph, 0, dist, prev);
    output_result(&graph, dist, prev);
    return 0;
}

实验结果

A 0 A B A C A C B A B D A C B D A C B D E

实验结论

本次实验通过实现Dijkstra算法，成功地找到了图中两点之间的最短路径，并输出了结果。在实现过程中，我们熟悉了C语言的编程方法，掌握了最短路径算法的原理和实现方法，加深了对图的概念和算法的理解。