正文

C语言实现Dijkstra算法：轻松入门图论，快速计算最短路径

/0 浏览量
0414

在图论中，Dijkstra算法是一种用于找到图中两个顶点之间最短路径的算法。它由荷兰计算机科学家爱德华·迪科斯彻在1959年发明。Dijkstra算法适用于带权图，并且权值非负。下面，我们将用C语言来实现Dijkstra算法，帮助大家轻松入门图论，快速计算最短路径。

Dijkstra算法的基本原理

Dijkstra算法的基本思想是维护一个集合S，其中包含所有已找到最短路径的顶点。初始时，S为空集，算法逐步扩大S，直到S包含所有顶点。

  1. 初始化：将源点加入集合S，其他顶点加入集合U（未访问顶点集）。源点到自身的距离为0，其他顶点的距离为无穷大。
  2. 选择U中的顶点u，使得d(u)最小，将其加入集合S。
  3. 对于U中未加入S的每个顶点v，如果v在u的邻接点中，则计算d(u) + w(u,v)，如果这个值小于d(v)，则更新d(v)。
  4. 重复步骤2和3，直到U为空。

C语言实现Dijkstra算法

下面是一个简单的C语言实现Dijkstra算法的示例：

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

#define MAX_VERTICES 10

// 函数声明
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices);

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {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}
    };

    int src = 0; // 源点
    int vertices = 9; // 顶点数

    dijkstra(graph, src, vertices);

    return 0;
}

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {
    int dist[vertices]; // 存储最短路径长度
    int visited[vertices]; // 标记顶点是否已访问

    // 初始化dist和visited数组
    for (int i = 0; i < vertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    dist[src] = 0; // 源点到自身的距离为0

    // 遍历所有顶点
    for (int i = 0; i < vertices; i++) {
        // 寻找未访问顶点中距离最小的顶点
        int min_dist = INT_MAX;
        int min_index = -1;
        for (int j = 0; j < vertices; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }

        // 将找到的顶点加入集合S
        visited[min_index] = 1;

        // 更新未访问顶点的距离
        for (int j = 0; j < vertices; j++) {
            if (!visited[j] && graph[min_index][j] && dist[min_index] != INT_MAX && dist[min_index] + graph[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + graph[min_index][j];
            }
        }
    }

    // 打印最短路径长度
    for (int i = 0; i < vertices; i++) {
        if (i != src) {
            printf("源点%d到顶点%d的最短路径长度为：%d\n", src, i, dist[i]);
        }
    }
}

在上面的代码中，我们定义了一个dijkstra函数，该函数接受图、源点和顶点数作为参数，并计算并打印出从源点到其他所有顶点的最短路径长度。

总结

通过以上内容，我们介绍了Dijkstra算法的基本原理和C语言实现。希望这篇文章能帮助大家轻松入门图论，快速计算最短路径。在实际应用中，Dijkstra算法有着广泛的应用，例如在路由算法、网络优化等方面。

-- 展开阅读全文 --