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

【图论】迪杰斯特拉算法

亿万年的星光2天前算法42

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

一、核心思想

贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；
松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；
重复上述步骤，直到所有节点都被标记为 “已确定”。

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

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

初始化：

距离数组 dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点 dist[i] = ∞（无穷大）；
标记数组 visited[]：所有节点初始为 false（未确定最短路径）；
优先队列（小顶堆）：存储 (当前距离, 节点)，初始入队 (0, s)。（朴素解法不使用优先队列）

迭代求解：

取出优先队列中距离最小的节点 u，若 u 已访问则跳过；
标记 u 为已访问（visited[u] = true）；
遍历 u 的所有邻接节点 v，若 dist[v] > dist[u] + 权值(u,v)，则更新 dist[v] = dist[u] + 权值(u,v)，并将 (dist[v], v) 入队；

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

三、例子详解

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

dist[v]：从源点 A 到点 v 的当前已知最短距离估计值。
final[v]：该距离是否已确定为最终最短距离（是/否）。

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

第 0 步：初始化

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

节点	`dist`	`final`	说明
A	0	否	源点
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

更新后状态：

节点	`dist`	`final`	说明
A	0	是	已确定
B	4	否	通过 A 更新
C	2	否	通过 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

更新后状态：

节点	`dist`	`final`	说明
A	0	是
B	3	否	通过 C 更新
C	2	是	已确定
D	10	否	通过 C 更新
E	12	否	通过 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 (更新)

更新后状态：

节点	`dist`	`final`	说明
A	0	是
B	3	是	已确定
C	2	是
D	8	否	通过 B 更新
E	12	否
当前处理节点： B
选择逻辑：从未确定的 `{D(8), E(12)}` 中，选择 `dist` 最小的点 D。

第 4 步：处理节点 D

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

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

更新后状态：

节点	`dist`	`final`	说明
A	0	是
B	3	是
C	2	是
D	8	是	已确定
E	10	否	通过 D 更新
当前处理节点： D
选择逻辑：从未确定的 `{E(10)}` 中，选择 `dist` 最小的点 E。

第 5 步：处理节点 E

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

最终状态：

节点	`dist`	`final`	说明
A	0	是
B	3	是
C	2	是
D	8	是
E	10	是	已确定
当前处理节点： E
选择逻辑：所有点均已确定，算法结束。

最终结果

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

A: 0
C: 2
B: 3
D: 8
E: 10

过程总结：

初始化所有点的距离 (dist) 和确定状态 (final)。
重复以下步骤，直到所有点 final 为“是”：
a. 选择：在所有 final 为“否”的点中，选出 dist 值最小的点 u。
b. 确定：将点 u 的 final 标记为“是”。此时 dist[u] 就是 A 到 u 的最终最短距离。
c. 松弛：对于 u 的每个邻居 v（且 v 未确定），尝试用 dist[u] + weight(u, v) 去更新 dist[v]，如果更小则更新。
表格中 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问题

没有最新的文章了...

【算法】动态规划（二）——数字三角形问题

1.问题描述及状态定义数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：从第一行开的数开始走，每次可以往下或右走一格，直到走到...

【算法】单调栈

一、单调栈单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：找到数组中每个元素的下一...

【算法】高精度（2）

五、高精度处理进位与借位其实也很简单，我们再来模拟一下，1439+887的时候，首先我们最低位相加，得到16，那么答案最低位就是6，再进个1，然后两数的十位相加，...

【贪心】----最优装载、背包、乘船问题

1.最优装载题目描述：有n个物体，第i个物体的重量为wi（wi为正整数）。选择尽量多的物体，使得总重量不超过C。【分析】由于只关心选择的物品的最大数量（而不是最大重量，最大重量需要考虑DP），所以装重...

【算法】博弈论——取石子游戏

【题目描述】有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取...

【贪心】----找零钱问题

一、找零钱问题例题1：有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。X = 628最佳支付方法：3张200块的，1张20块的，1张5...

青少年编程知识记录

【图论】迪杰斯特拉算法

一、核心思想

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

第 0 步：初始化

第 1 步：处理节点 A

第 2 步：处理节点 C

第 3 步：处理节点 B

第 4 步：处理节点 D

第 5 步：处理节点 E

最终结果

相关文章

【算法】动态规划（二）——数字三角形问题

【算法】单调栈

【算法】高精度（2）

【贪心】----最优装载、背包、乘船问题

【算法】博弈论——取石子游戏

【贪心】----找零钱问题

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.

青少年编程知识记录

【图论】迪杰斯特拉算法

一、核心思想

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

第 0 步：初始化

第 1 步：处理节点 A

第 2 步：处理节点 C

第 3 步：处理节点 B

第 4 步：处理节点 D

第 5 步：处理节点 E

最终结果

相关文章

【算法】动态规划（二）——数字三角形问题

【算法】单调栈

【算法】高精度（2）

【贪心】----最优装载、背包、乘船问题

【算法】博弈论——取石子游戏

【贪心】----找零钱问题

鲁ICP备20008475号var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?bf4de1f8c92c90db1ab8165f21fb936d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})();

Powered By Z-BlogPHP. Theme by TOYEAN.

鲁ICP备20008475号