当前位置：首页 > 算法 > 正文内容

【图论】迪杰斯特拉算法

亿万年的星光2个月前 (12-05)算法428
迪杰斯特拉算法是由荷兰计算机科学家艾兹赫尔・迪杰斯特拉于 1956 年提出的单源最短路径算法，用于求解带权有向、 无向图中，从一个源节点到其余所有节点的最短路径问题（要求图中所有边的权值非负）。

一、核心思想

  1. 贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；

  2. 松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；

  3. 重复上述步骤，直到所有节点都被标记为 “已确定”。

二、算法步骤（以无向带权图为例）

假设图有 n 个节点，源节点为 s：

  1. 初始化：

    • 距离数组 dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点 dist[i] = ∞（无穷大）；

    • 标记数组 visited[]：所有节点初始为 false（未确定最短路径）；

    • 优先队列（小顶堆）：存储 (当前距离, 节点)，初始入队 (0, s)。（朴素解法不使用优先队列）

  2. 迭代求解：

    • 取出优先队列中距离最小的节点 u，若 u 已访问则跳过；

    • 标记 u 为已访问（visited[u] = true）；

    • 遍历 u 的所有邻接节点 v，若 dist[v] > dist[u] + 权值(u,v)，则更新 dist[v] = dist[u] + 权值(u,v)，并将 (dist[v], v) 入队；

  3. 终止条件：优先队列为空，此时 dist[] 数组存储源节点到所有节点的最短路径。（朴素解法不使用优先队列）


三、例子详解



状态表跟踪：我们关注每个点的两个状态：

  1. dist[v]：从源点 A 到点 v 的当前已知最短距离估计值。

  2. final[v]：该距离是否已确定为最终最短距离（是/否）。

算法每一步：在所有 final 为“否” 的点中，选出 dist 值最小 的一个点进行处理。



第 0 步：初始化

设置 dist[A] = 0，其他点为 ∞。所有点均未确定。

节点distfinal说明
A0否源点
B∞否
C∞否
D∞否
E∞否
当前处理节点： 无


选择逻辑： 准备从所有未确定的点中选择 dist 最小的点。





第 1 步：处理节点 A

在所有未确定的点 {A(0), B(∞), C(∞), D(∞), E(∞)} 中，dist 最小的是 A。将其标记为已确定。 检查 A 的所有出边，更新邻居的 dist 值：

  • A->B: dist[B] = min(∞, 0+4) = 4

  • A->C: dist[C] = min(∞, 0+2) = 2

更新后状态：

节点distfinal说明
A0是已确定
B4否通过 A 更新
C2否通过 A 更新
D∞否
E∞否
当前处理节点： A


选择逻辑： 从未确定的 {B(4), C(2), D(∞), E(∞)} 中，选择 dist 最小的点 C。




第 2 步：处理节点 C

从未确定的点中，dist 最小的是 C(2)。将其标记为已确定。 检查 C 的所有出边，更新未确定邻居的 dist 值：

  • C->B: dist[B] = min(4, 2+1) = 3 (更新)

  • C->D: dist[D] = min(∞, 2+8) = 10

  • C->E: dist[E] = min(∞, 2+10) = 12

更新后状态：

节点distfinal说明
A0是
B3否通过 C 更新
C2是已确定
D10否通过 C 更新
E12否通过 C 更新
当前处理节点： C


选择逻辑： 从未确定的 {B(3), D(10), E(12)} 中，选择 dist 最小的点 B。





第 3 步：处理节点 B

从未确定的点中，dist 最小的是 B(3)。将其标记为已确定。 检查 B 的所有出边：

  • B->C: C 已确定，跳过。

  • B->D: dist[D] = min(10, 3+5) = 8 (更新)

更新后状态：

节点distfinal说明
A0是
B3是已确定
C2是
D8否通过 B 更新
E12否
当前处理节点： B


选择逻辑： 从未确定的 {D(8), E(12)} 中，选择 dist 最小的点 D。



第 4 步：处理节点 D

从未确定的点中，dist 最小的是 D(8)。将其标记为已确定。 检查 D 的所有出边：

  • D->E: dist[E] = min(12, 8+2) = 10 (更新)

更新后状态：

节点distfinal说明
A0是
B3是
C2是
D8是已确定
E10否通过 D 更新
当前处理节点： D


选择逻辑： 从未确定的 {E(10)} 中，选择 dist 最小的点 E。




第 5 步：处理节点 E

最后一个未确定的点是 E(10)。将其标记为已确定。 检查 E 的出边 E->D，D 已确定，跳过。

最终状态：

节点distfinal说明
A0是
B3是
C2是
D8是
E10是已确定
当前处理节点： E


选择逻辑： 所有点均已确定，算法结束。




最终结果

从源点 A 到各点的最短距离：

  • A: 0

  • C: 2

  • B: 3

  • D: 8

  • E: 10

过程总结：

  1. 初始化所有点的距离 (dist) 和确定状态 (final)。

  2. 重复以下步骤，直到所有点 final 为“是”：

    a. 选择：在所有 final 为“否”的点中，选出 dist 值最小的点 u。

    b. 确定：将点 u 的 final 标记为“是”。此时 dist[u] 就是 A 到 u 的最终最短距离。

    c. 松弛：对于 u 的每个邻居 v（且 v 未确定），尝试用 dist[u] + weight(u, v) 去更新 dist[v]，如果更小则更新。

  3. 表格中 dist 列的最终值即为最短路径距离。



四、参考代码


1.朴素解法


#include <iostream>
#include <climits>

using namespace std;

const int MAX_N = 100;  // 最大节点数
int graph[MAX_N][MAX_N];  // 邻接矩阵
int dist1[MAX_N];  // 方法1的距离数组
int dist2[MAX_N];  // 方法2的距离数组
bool visited[MAX_N];  // 访问标记数组
int n;  // 实际节点数

// 朴素Dijkstra算法实现（不使用STL）
void dijkstra_naive_no_stl(int src) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist1[i] = INT_MAX;  // 距离初始化为无穷大
        visited[i] = false; // 所有节点都未访问
    }
    
    // 源点距离设为0
    dist1[src] = 0;
    
    // 需要处理n个节点
    for (int i = 0; i < n; i++) {
        // 步骤1：在所有未确定的节点中找到距离最小的节点
        int u = -1;
        int min_dist = INT_MAX;
        
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist1[j] < min_dist) {
                min_dist = dist1[j];
                u = j;
            }
        }
        
        // 如果没有找到可处理的节点（图不连通），提前结束
        if (u == -1) break;
        
        // 步骤2：标记该节点为已确定
        visited[u] = true;
        
        // 步骤3：松弛操作 - 更新所有邻居的距离
        for (int v = 0; v < n; v++) {
            // 如果u到v有边（graph[u][v] != 0）
            if (graph[u][v] != 0 && !visited[v] && dist1[u] != INT_MAX) {
                int new_dist = dist1[u] + graph[u][v];
                if (new_dist < dist1[v]) {
                    dist1[v] = new_dist;
                }
            }
        }
    }
}

// 使用邻接矩阵的版本（更朴素）
void dijkstra_adj_matrix(int src) {
    // 初始化visited数组
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    
    // 初始化距离数组
    for (int i = 0; i < n; i++) {
        dist2[i] = graph[src][i] == 0 ? INT_MAX : graph[src][i];
    }
    
    dist2[src] = 0;
    visited[src] = true;
    
    // 处理剩余的n-1个节点
    for (int count = 0; count < n - 1; count++) {
        // 找到未访问节点中距离最小的
        int u = -1;
        int min_dist = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i] && dist2[i] < min_dist) {
                min_dist = dist2[i];
                u = i;
            }
        }
        
        if (u == -1) break;
        visited[u] = true;
        
        // 更新通过u到其他节点的距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && dist2[u] != INT_MAX) {
                int new_dist = dist2[u] + graph[u][v];
                if (new_dist < dist2[v]) {
                    dist2[v] = new_dist;
                }
            }
        }
    }
}

// 初始化图
void init_graph() {
    // 初始化邻接矩阵为0（表示无边）
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            graph[i][j] = 0;
        }
    }
    
    // 示例：构建与之前相同的图
    n = 5;  // 节点数：A(0), B(1), C(2), D(3), E(4)
    
    // 添加边（使用邻接矩阵表示）
    // 注意：这里0表示无边，其他值表示边的权重
    graph[0][1] = 4;  // A->B (4)
    graph[0][2] = 2;  // A->C (2)
    
    graph[1][2] = 1;  // B->C (1)
    graph[1][3] = 5;  // B->D (5)
    
    graph[2][1] = 1;  // C->B (1)
    graph[2][3] = 8;  // C->D (8)
    graph[2][4] = 10; // C->E (10)
    
    graph[3][4] = 2;  // D->E (2)
    
    graph[4][3] = 2;  // E->D (2)
}

int main() {
    // 初始化图
    init_graph();
    
    // 从节点0（A）开始计算最短路径
    int src = 0;
    
    cout << "方法1：邻接表思路的朴素实现" << endl;
    dijkstra_naive_no_stl(src);
    
    cout << "方法2：邻接矩阵的朴素实现" << endl;
    dijkstra_adj_matrix(src);
    
    // 输出结果
    char node_names[] = {'A', 'B', 'C', 'D', 'E'};
    
    cout << "\n从节点 " << src << " (A) 到各节点的最短距离：" << endl;
    cout << "节点\t方法1\t方法2" << endl;
    cout << "----------------------" << endl;
    
    for (int i = 0; i < n; i++) {
        cout << node_names[i] << "\t";
        
        if (dist1[i] == INT_MAX) {
            cout << "INF";
        } else {
            cout << dist1[i];
        }
        
        cout << "\t";
        
        if (dist2[i] == INT_MAX) {
            cout << "INF";
        } else {
            cout << dist2[i];
        }
        
        cout << endl;
    }
    
    return 0;
}


2.优先队列解法



#include <iostream>

#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii;  // 自定义类型别名 
/**
 * Dijkstra 算法 - 邻接表 + 优先队列版本
 *  n 节点数量 (0 ~ n-1)
 *  adj 邻接表，adj[u] = vector<{v, w}> 表示 u->v 的边权重为 w
 *  src 源点
 * 返回： 从源点到所有节点的最短距离
 */
vector<int> dijkstra(int n, vector<vector<pii>>& adj, int src) {
    vector<int> dist(n, INT_MAX); //距离数组初始化 
    vector<bool> visited(n, false); //标记数组初始化 
    priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆（默认按照第一个元素从小到达排序） 
    dist[src] = 0;
    pq.push(make_pair(0, src)); //make_pair自动推导类型 
    while (!pq.empty()) {
        pii current = pq.top(); //优先队列的队头 
        pq.pop();
        int d = current.first; // 从源点到节点 u 的当前最短距离
        int u = current.second; // 节点 
        // 如果这个距离已经过时，跳过
        if (d > dist[u]) continue;
        // 标记为已访问
        visited[u] = true;
        // 遍历所有邻居
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first; // 获取邻居节点编号
            int w = adj[u][i].second; // 获取从 u 到 v 的边权重
            if (!visited[v]) {
                int new_dist = dist[u] + w;
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;  //更新到v点的距离 
                    pq.push(make_pair(new_dist, v));//pq中先存距离，再存节点 
                }
            }
        }
    }
    return dist;
}

int main() {
    int n = 5;  // 节点数
    vector<vector<pii>> adj(n);
    // 构建图
    adj[0].push_back(make_pair(1, 4));
    adj[0].push_back(make_pair(2, 2));
    adj[1].push_back(make_pair(2, 1));
    adj[1].push_back(make_pair(3, 5));
    adj[2].push_back(make_pair(1, 1));
    adj[2].push_back(make_pair(3, 8));
    adj[2].push_back(make_pair(4, 10));
    adj[3].push_back(make_pair(4, 2));
    adj[4].push_back(make_pair(3, 2));
    
    int src = 0;
    vector<int> dist = dijkstra(n, adj, src);

    cout << "从节点 " << src << " 到各节点的最短距离：" << endl;
    for (int i = 0; i < n; i++) {
        if (dist[i] == INT_MAX)
            cout << i << ": INF" << endl;
        else
            cout << i << ": " << dist[i] << endl;
    }
    return 0;
}


注意：

typedef pair<int, int> pii;  // 自定义类型别名 

表示自定义类型别名，编程中常用的是
typedef long long ll; 
这种

另外，两处first和secod的含义不一样，对于pii来说，只是表示两个int的二元组类型，具体含义是使用者决定的。



3.带路径的迪杰斯特拉算法

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm> // 用于reverse反转路径
using namespace std;
typedef pair<int, int> pii;  // 自定义类型别名 

/**
 * Dijkstra 算法 - 邻接表 + 优先队列版本（带路径记录）
 *  n 节点数量 (0 ~ n-1)
 *  adj 邻接表，adj[u] = vector<{v, w}> 表示 u->v 的边权重为 w
 *  src 源点
 *  path 输出参数：path[v] 存储节点v的前驱节点（用于回溯路径）
 * 返回： 从源点到所有节点的最短距离
 */
vector<int> dijkstra(int n, vector<vector<pii>>& adj, int src, vector<int>& path) {
    vector<int> dist(n, INT_MAX); // 距离数组：src到各节点的最短距离
    vector<bool> visited(n, false); // 标记节点是否已确定最短距离
    priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆（按距离升序）

    // 初始化：路径数组初始化为-1（表示无前置节点）
    path.assign(n, -1);
    dist[src] = 0;
    pq.push(make_pair(0, src)); 

    while (!pq.empty()) {
        pii current = pq.top(); 
        pq.pop();
        int d = current.first; // 源点到u的当前距离
        int u = current.second; // 当前节点

        // 距离过时，跳过（已找到更短路径）
        if (d > dist[u]) continue;
        visited[u] = true;

        // 遍历u的所有邻居
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first; // 邻居节点
            int w = adj[u][i].second; // 边权重
            if (!visited[v]) {
                int new_dist = dist[u] + w;
                // 找到更短路径：更新距离 + 记录前驱节点
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    path[v] = u; // 记录v的前驱是u
                    pq.push(make_pair(new_dist, v));
                }
            }
        }
    }
    return dist;
}

/**
 * 回溯路径：从目标节点target反向找到源点src，再反转得到正序路径
 *  src 源点
 *  target 目标节点
 *  path 前驱节点数组
 * 返回： src到target的最短路径（正序）
 */
vector<int> getShortestPath(int src, int target, const vector<int>& path) {
    vector<int> res;
    // 若目标节点不可达，返回空路径
    if (path[target] == -1 && src != target) {
        return res;
    }
    // 从target回溯到src
    for (int cur = target; cur != -1; cur = path[cur]) {
        res.push_back(cur);
    }
    // 反转得到正序路径（src -> ... -> target）
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n = 5;  // 节点数（0~4）
    vector<vector<pii>> adj(n);
    // 构建图
    adj[0].push_back(make_pair(1, 4));
    adj[0].push_back(make_pair(2, 2));
    adj[1].push_back(make_pair(2, 1));
    adj[1].push_back(make_pair(3, 5));
    adj[2].push_back(make_pair(1, 1));
    adj[2].push_back(make_pair(3, 8));
    adj[2].push_back(make_pair(4, 10));
    adj[3].push_back(make_pair(4, 2));
    adj[4].push_back(make_pair(3, 2));
    
    int src = 0;
    vector<int> path; // 存储各节点的前驱节点
    vector<int> dist = dijkstra(n, adj, src, path);

    // 输出最短距离 + 最短路径
    cout << "从节点 " << src << " 到各节点的最短距离和路径：" << endl;
    for (int i = 0; i < n; i++) {
        cout << "节点 " << i << "：";
        if (dist[i] == INT_MAX) {
            cout << "INF（无路径）" << endl;
        } else {
            cout << "距离=" << dist[i] << "，路径：";
            vector<int> shortest_path = getShortestPath(src, i, path);
            // 输出路径
            for (int j = 0; j < shortest_path.size(); j++) {
                if (j > 0) cout << " -> ";
                cout << shortest_path[j];
            }
            cout << endl;
        }
    }
    return 0;
}

/*

从节点 0 到各节点的最短距离和路径：
节点 0：距离=0，路径：0
节点 1：距离=3，路径：0 -> 2 -> 1
节点 2：距离=2，路径：0 -> 2
节点 3：距离=8，路径：0 -> 2 -> 1 -> 3
节点 4：距离=10，路径：0 -> 2 -> 1 -> 3 -> 4


*/
1.path 数组：
类型：vector<int>，path[v] = u 表示 “到达节点 v 的最短路径中，v 的上一个节点是 u”；
初始化：所有元素设为 -1（表示无前置节点，源点的前驱始终为 -1）；
更新逻辑：当找到节点 v 的更短路径时，同步更新 path[v] = u（u 是当前节点）。
2.getShortestPath 函数：
功能：从目标节点 target 反向回溯到源点 src（通过 path 数组）；
处理：回溯得到的路径是逆序（target -> ... -> src），需用 reverse 反转得到正序路径；
边界：若 path[target] == -1 且 target != src，说明目标节点不可达，返回空路径。


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：【算法】动态规划—区间DP问题

下一篇：【图论】弗洛伊德算法（Floyd）

相关文章

【算法】归并排序

【算法】归并排序

一、基本思想归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤： 1.分解：将待排序的序列不断二分，直到每个子序列只包含一个元素（此时自然有序） ...

【贪心】 导弹拦截

【贪心】 导弹拦截

【题目描述】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来...

【贪心】----排队打水

【贪心】----排队打水

一、基础版排队打水【题目描述】学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。...

【排序】----选择排序

【排序】----选择排序

1.基本思想每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列最前，直到全部待排序的数据排完。2.过程首先初始化最小元素索引值为首元素。依次遍历待排序数列，遇到小于该最小索引...

【算法】滑动窗口1—窗口大小固定

【算法】滑动窗口1—窗口大小固定

一、定义滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动...

【分治】----快速幂

【分治】----快速幂

1.幂幂（power）是指乘方运算的结果。n^m指该式意义为m个n相乘。把n^m看作乘方的结果，叫做n的m次幂，也叫n的m次方。2.幂的数学表示和规则2^3  *   2...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.