Dijkstra算法

今天把树和图的基础知识过了一遍,着重学习了一下Dijkstra算法

什么是Dijkstra

Dijkstra算法是一种用于解决带权重的有向图中单源最短路径问题的算法。它以荷兰计算机科学家Edsger W. Dijkstra的名字命名。

该算法从源节点开始，对所有节点进行初始化，并将源节点到其他节点的距离初始化为无穷大。然后，它逐步确定到达每个节点的最短路径，直到找到源节点到目标节点的最短路径或遍历完所有节点。在每一步中，Dijkstra算法选择未被访问过且距离源节点最近的节点，将其标记为已访问，并更新与该节点相邻节点的距离。如果通过当前节点可以获得更短的距离，则更新该节点的距离值。

Dijkstra 算法是求一个图中一个点到其他所有点的最短路径的算法，阅读前请想了解图的数据结构「邻接矩阵」

 要点

每次从  未求出最短路径的点 中 取出 距离距离起点 最小路径的点，以这个点为桥梁 刷新 未求出最短路径的点 的距离

案例：以 A 点为顶点，求到其他点的最短路径。

邻接矩阵图

• result：已求出 最小路径的顶点
• notFound：未求出 最小路径的顶点，里面的值是 到起点的距离

初始，result={A(0)} 中只有起点 A，notFound={B(2),C(∞),D(6)} 中是除了 A 点的其他点，里面的值是到起点的距离（例如 B(2) 代表 B点到起点的距离为 2）

然后，从 未求出最短路径的点 notFound 中取出 最短路径的点 B(2) ，然后通过 B(2) 为桥梁 刷新 未求出最短路径的点 的距离 

通过 B(2) 为桥梁，刷新距离。

例如 AD = 6 > AB + BD = 4 以 B(2) 为桥梁的距离更短，就刷新 未求出最短路径点 D(6) 的距离为 D(4)

notFound={C(∞),D(4)}  以此类推

代码实现

#include <stdio.h>
#include <limits.h>
 
#define V 4 // 图中节点的数量
 
// Dijkstra算法实现
void dijkstra(int graph[V][V], int startVertex, int result[]) {
    int i, j;
    int notFound[V];
 
    // 初始化结果数组和未找到最短路径的数组
    for (i = 0; i < V; i++) {
        result[i] = -1;
        notFound[i] = graph[startVertex][i];
    }
    result[startVertex] = 0;
    notFound[startVertex] = -1;
 
    // Dijkstra算法主循环
    for (i = 1; i < V; i++) {
        // 选取当前未找到最短路径的数组中距离最小的点
        int min = INT_MAX;
        int minIndex = 0;
        for (j = 0; j < V; j++) {
            if (notFound[j] > 0 && notFound[j] < min) {
                min = notFound[j];
                minIndex = j;
            }
        }
 
        // 将找到的最短路径的点加入结果数组中
        result[minIndex] = min;
        notFound[minIndex] = -1;
 
        // 刷新未找到最短路径的数组中的距离
        for (j = 0; j < V; j++) {
            if (graph[minIndex][j] > 0 && result[j] == -1) {
                int newDistance = result[minIndex] + graph[minIndex][j];
                if (newDistance < notFound[j] || notFound[j] == -1) {
                    notFound[j] = newDistance;
                }
            }
        }
    }
}
 
int main() {
    char vertices[] = { 'A', 'B', 'C', 'D' };
    int graph[V][V] = { {0, 2, -1, 6},
                        {2, 0, 3, 2},
                        {-1, 3, 0, 2},
                        {6, 2, 2, 0} };
    int result[V];
 
    // 使用Dijkstra算法计算最短路径
    dijkstra(graph, 0, result);
 
    // 打印最短路径结果
    printf("最短路径结果：\n");
    for (int i = 0; i < V; i++) {
        printf("%c: %d\n", vertices[i], result[i]);
    }
 
    return 0;
}