迪杰斯特拉算法（Dijkstra）详解：原理、步骤与代码实现

迪杰斯特拉算法（Dijkstra）详解：原理、步骤与代码实现

引用

CSDN

1.

https://blog.csdn.net/dcb666666/article/details/139770257

迪杰斯特拉算法（Dijkstra）是解决带权有向图中单源最短路径问题的经典算法。本文将从算法的背景、原理、优缺点以及具体实现等多个维度，深入浅出地讲解这一重要算法。

一、算法用途

迪杰斯特拉算法主要用于解决最短路径问题，常用于路由算法或者作为其他图的算法的一个子模块。

二、算法背景

迪杰斯特拉算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出的一种解决带权有向图中单源最短路径问题的算法。该算法采用贪心策略，逐步找到从源点到其余各个顶点的最短路径。迪杰斯特拉算法的主要特点是从起始点开始，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

带权有向图：带权有向图不仅能表示节点间的连接关系，还能通过权重表达关系的强弱或代价。

贪心策略：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

三、算法原理

迪杰斯特拉算法的主要特点是从源点开始，每次都遍历到距源点的路线距离最近且未访问过（即未在顶点集）的顶点，直到扩展到终点为止。在算法执行过程中，通过不断更新距离值，逐步逼近最短路径的实际长度。

（注：该算法要求不存在负权边）

四、算法优、缺点

1. 优点

迪杰斯特拉算法思想简单、易于理解，可以很好地解决源点到其他顶点的最短路径问题。

2. 缺点

迪杰斯特拉算法只适用于权值为正的有向、无向图，权值为负则需要选择其他算法。

五、题目解析

如上图所示：

• V1、V2、V3、V4、V5、V6：带权有向图的5个顶点；
• 路径：
• V1->V3值为10
• V1->V6值为100
• V2->V3值为50
• V3->V4值为50
• V4->V6值为10
• V5->V4值为20
• V5->V6值为60

传统列表结果如下：

• 源点为V1，终点为V2：没有V1到V2线，所以值为无穷大
• 源点为V1，终点为V3：V1->V3值为10（最小）
• 源点为V1，终点为V4：
• V1->V3->V4值为60
• V1->V5->V4值为50（最小）
• 源点为V1，终点为V5：V1->V5值为30（最小）
• 源点为V1，终点为V6：
• V1->V3->V4->V5->V6值为140
• V1->V3->V4->V6值为70
• V1->V5->V4->V6值为60（最小）
• V1->V5->V6值为90

故：

使用迪杰斯特拉算法进行解答：

第一步，通过分析上图，声明并初始化Distance数组以及顶点集T（由于没有到达V2的路线，我们最后考虑）；

顶点集T { V1 }

第二步，通过对Distance数组的分析可知，V1可到达的有效顶点为V3（10）、V5（30）、V6（100），根据路径值选择最短路径V1->V3值为10，此时将V3加入顶点集。由于V3进入顶点集，同样带来了新的顶点V4及到达V4路线V1->V3->V4（60），更新Distance数组以及顶点集；

顶点集T { V1、V3 }

第三步，再次对Distance数组的分析可知，除V3外，此时V1可到达的有效顶点为V4（60）、V5（30）、V6（100），根据路径值选择最短路径V1->V5值为30，此时将V5加入顶点集。由于V5进入顶点集，同样带来了新的到达V4和V6路线，即V1->V5->V4（50）与V1->V5->V6（90），故更新Distance数组以及顶点集；

顶点集T { V1、V3、V5 }

第四步，再次对Distance数组的分析可知，除V3与V5外，此时V1可到达的有效顶点为V4（50）、V6（90），根据路径值选择最短路径V1->V5->V4值为50，由于V4进入顶点集，同样带来了新的到达V6的路线即V1->V5->V4->V6（60），故更新Distance数组以及顶点集；

顶点集T { V1、V3、V5 、V4}

第五步，将V6放入顶点集，将V2放入顶点集，更新顶点集；

顶点集T { V1、V3、V5 、V4、V6、V2}

求毕（注：计算过程中一定要细心哦）

六、代码实现

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

#define T 6  // 顶点的数量（在这里修改顶点数量）

// 找到Distance数组中的权值最小值
int minDistance(int distance[], int sign[]) {
    int min = INT_MAX, min_index;

    for (int t = 0; t <T; t++) {
        if (sign[t] == 0 && distance[t] <= min) {
            min = distance[t];
            min_index = t;
        }
    }

    return min_index;
}

// 打印最终的最短路径
void printResult(int distance[]) {
    printf("顶点\t最短距离\n");
    for (int i = 0; i < T; i++){
        if(distance[i] < 65535){
            printf("%d\t%d\n", i+1, distance[i]);//注意：此处i+1原代码应该是i,因为原顶点是从0开始计数，本题是从1开始
        }
        else{
            printf("%d\t%s\n", i+1, "无穷大");
        }	
    }	
}

// 迪杰斯特拉（Dijkstra）算法的实现
void dijkstra(int graph[T][T], int DCBYXB) {//注意：DCBYXB为我的标记，有特殊意义，供我自己用
    int distance[T];     // 存储从源点到每个顶点的最短距离
    int sign[T];   // 记录该顶点是否已经包含在最短路径树中

    // 初始化所有距离为无穷大，标记所有顶点为未包含在最短路径树中
    for (int i = 0; i < T; i++) {
        distance[i] = INT_MAX;
        sign[i] = 0;
    }

    // 设置在最短路径树中点的距离为0
    distance[DCBYXB] = 0;//注意：DCBYXB为我的标记，有特殊意义，供我自己用

    // 找到最短路径
    for (int count = 0; count < T - 1; count++) {
        // 选择距离最小的节点
        int u = minDistance(distance, sign);

        // 标记节点为已包含
        sign[u] = 1;

        // 更新相邻节点的距离
        for (int t = 0; t < T; t++) {
            if (!sign[t] && graph[u][t] && distance[u] != INT_MAX &&
                distance[u] + graph[u][t] < distance[t]) {
                distance[t] = distance[u] + graph[u][t];
            }
        }
    }

    // 打印最终的最短路径
    printResult(distance);
}

int main() {
    int graph[T][T] = {//注意：数组下标是从零开始计数的
        {0, 0, 10,   0, 30, 100},//单向图注意：顶点自身、没有直接连线、线头方向为负方向均为0
        {0, 0, 50,   0,  0,   0},//无向图注意：顶点自身、没有直接连线均为0
        {0, 0,  0,  50,  0,   0},
        {0, 0,  0,   0,  0,  10},
        {0, 0,  0,  20,  0,  60},
        {0, 0,  0,   0,  0,   0}
    };
    dijkstra(graph, 0);

    return 0;
}