Djikstra算法 - Biscuitの赛博小窝

Biscuit

哈基米，你要大步大步地走下去啊，不行，要悠哒悠哒才能欣赏到沿途的风景。

公告

欢迎来到我的博客喵。

了解更多

1632 字

8 分钟

Djikstra算法

2025-10-29

数据结构与算法

最短路径算法

/

Djikstra算法

算法思想#

Djikstra算法是一种用于计算加权图中单源最短路径的经典算法。它适用于边权非负的图，能够有效地找到从起始节点到其他节点的最短路径。

是一种贪心算法

算法数据结构#

对于一个有向加权图G=(V,E)，其中V是顶点集合 $\{1,2,\ldots,n\}$ ，E是边集合，w(u,v)表示边(u,v)的权重。

采用邻接矩阵C表示图G，邻接矩阵的定义如下：

C[i][j] = \begin{cases} w(i,j) & \text{如果边}(i,j) \in E \\ \infty & \text{如果边}(i,j) \notin E \end{cases}

有向性体现在矩阵的非对称性上，从行到列是有向边的方向

算法步骤#

初始化：
- 从顶点中找一个点作为原点，创建一个距离数组 $D[n]$ ， $D[i]$ 表示从起始节点到第 $i$ 个节点的最短距离。 $D[i]=C[start][i]$ 。
- 将起始节点的距离设为0，即 $D[start] = 0$ 。
- 维护一个一维数组 $P[n]$ ，初始化为-1。 $P[i]$ 表示从起始节点到节点i的最短路径上，i的前一个节点。
- 创建一个布尔数组 $S[n]$ ，用于标记节点是否已被处理，初始化为false。
TIP
P数组用于记录路径信息，方便在算法结束后回溯最短路径。最后得到一颗树，表示从起始节点到所有其他节点的最短路径。
主循环
- 将顶点集V分为两个子集：已处理节点集S和未处理节点集V-S。初始化邻接矩阵 $C[i][j]$ ， $D[i]$ ， $P[i]$ 和 $S[i]$ 。
- 从V-S中选择一个顶点w,使得 $D[w]$ 最小，将w加入S。
- 对于每个未处理节点v ∈ V-S，检查通过w到达v的路径是否更短，即检查 $D[w] + C[w][v] < D[v]$ 。如果是，则更新 $D[v]$ 和 $P[v]$ 。

对于给定目标点求最短路径，Djikstra算法可以反过来用，即从终点回溯到起点，得到最短路径。

代码实现#

1
#ifndef GRAPH_H
2
#define GRAPH_H
3

4
/*
5
 * graph.h
6
 * 最短路径实验 — 图的类定义
7
 * 提供邻接矩阵和邻接表两种表示，包含 Dijkstra 和 Floyd-Warshall 算法接口。
8
 */
9

10
#include <vector>
11
#include <string>
12
#include <utility>
13

14
using namespace std;
15

16
/*
17
 Graph 类：表示带权图，支持无向/有向（由 addEdge 的实现决定）
18
* 成员：
19
*  n: 顶点数量
20
*   adjMatrix: 邻接矩阵（用于 Floyd-Warshall）
21
*   adjList: 邻接表（用于 Dijkstra）
22
*/
23
class Graph {
24
public:
25
    int n; // 顶点数量
26
    vector<vector<int>> adjMatrix;            // 邻接矩阵，未连通处用 INT_MAX 表示
27
    vector<vector<pair<int, int>>> adjList;   // 邻接表，每项为 (目标顶点, 权重)
28

29
    // 构造函数：初始化顶点数并设置邻接结构
30
    Graph(int vertices);
31

32
    // 添加一条边 u->v, 权重 w；当前实现也会同时添加 v->u（即无向图），如需有向图可修改此函数
33
    void addEdge(int u, int v, int w);
34

35
    // 从文件加载图，文件格式：第一行 "n edges"，随后每行 "u v w"
36
    void loadFromFile(const string& filename);
37

38
    // Dijkstra 算法（单源最短路径）
39
    // 输入：source 源点
40
    // 输出：pair(dist, prev)
41
    //  dist[i] 为 source 到 i 的最短距离（不可达为 INT_MAX）
42
    //  prev[i] 为重建路径时 i 的前驱节点，source 的 prev 为 -1
43
    pair<vector<int>, vector<int>> dijkstra(int source);
44

45
    // Floyd-Warshall 算法（任意两点最短路径）
46
    // 返回 pair(distMatrix, nextMatrix)
47
    //  distMatrix[i][j] 为 i->j 的最短距离（不可达为 INT_MAX）
48
    //  nextMatrix[i][j] 若为 -1 表示无路径，否则表示从 i 到 j 路径上的下一个节点
49
    pair<vector<vector<int>>, vector<vector<int>>> floydWarshall();
50

51
    // 使用 Dijkstra 的 prev 数组重建 source->target 路径，返回路径节点序列；若无路径返回空向量
52
    vector<int> getPath(int source, int target, const vector<int>& prev);
53

54
    // 使用 Floyd-Warshall 的 next 矩阵重建 source->target 路径；若无路径返回空向量
55
    vector<int> getPathFW(int source, int target, const vector<vector<int>>& next);
56
};
57

58
#endif // GRAPH_H

1
#include "graph.h"
2
#include <iostream>
3
#include <fstream>
4
#include <queue>
5
#include <limits>
6
#include <algorithm>
7
#include <climits>
8

9
// 根据给定顶点数创建邻接矩阵和邻接表
10
// 初始化，邻接矩阵中无边处使用 INT_MAX 表示，自身到自身的距离为 0
11
Graph::Graph(int vertices) : n(vertices) {
12
    adjMatrix.assign(n, vector<int>(n, INT_MAX));
13
    adjList.assign(n, vector<pair<int, int>>());
14
    for (int i = 0; i < n; ++i) {
15
        adjMatrix[i][i] = 0;
16
    }
17
}
18

19
// 将边信息写入邻接矩阵与邻接表
20
// 当前实现同时添加反向边以构造无向图
21
void Graph::addEdge(int u, int v, int w) {
22
    adjMatrix[u][v] = w;
23
    adjList[u].emplace_back(v, w);//u->v
24
    // 无向图同时添加反向边
25
    adjMatrix[v][u] = w;
26
    adjList[v].emplace_back(u, w);
27
}
28

29
// 从文件加载图数据，文件格式：第一行 "n edges"，后续每行为 "u v w"
30
void Graph::loadFromFile(const string& filename) {
31
    ifstream file(filename);
32
    if (!file.is_open()) {
33
        cerr << "Error opening file: " << filename << endl;
34
        return;
35
    }
36
    int edges;
37
    file >> n >> edges;
38
    adjMatrix.assign(n, vector<int>(n, INT_MAX));
39
    adjList.assign(n, vector<pair<int, int>>());
40
    for (int i = 0; i < n; ++i) {
41
        adjMatrix[i][i] = 0;
42
    }
43
    for (int i = 0; i < edges; ++i) {
44
        int u, v, w;
45
        file >> u >> v >> w;
46
        addEdge(u, v, w);
47
    }
48
    file.close();
49
}
50

51
// Dijkstra 算法（使用最小堆实现）
52
// 输入：source 源点
53
// 返回：pair(dist, prev)
54
//  dist[i] 为 source 到 i 的最短距离
55
//  prev[i] 在路径重建时表示 i 的前驱节点
56
pair<vector<int>, vector<int>> Graph::dijkstra(int source) {
57
    vector<int> dist(n, INT_MAX);
58
    vector<int> prev(n, -1);
59
    dist[source] = 0;
60
    // 优先队列按距离从小到大弹出（pair.first = 距离, pair.second = 顶点）
61
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
62
    pq.emplace(0, source);
63
    while (!pq.empty()) {
64
        auto top = pq.top();
65
        int cost = top.first;
66
        int node = top.second;
67
        pq.pop();
68
        if (cost > dist[node]) continue;//跳过过期节点
69
        for (auto& p : adjList[node]) {
70
            int v = p.first;//node的邻居
71
            int w = p.second;//node到邻居的边权
72
            if (dist[node] != INT_MAX && dist[node] + w < dist[v]) {
73
                dist[v] = dist[node] + w;
74
                prev[v] = node;//更新前驱节点
75
                pq.emplace(dist[v], v);
76
            }
77
        }
78
    }
79
    return {dist, prev};
80
}
81

82
// Floyd-Warshall 算法：计算任意两点最短路径
83
// 返回：pair(dist, next)
84
//  dist 为最短距离矩阵
85
//  next 用于路径重建，若 next[i][j] == -1 表示 i->j 无路径
86
pair<vector<vector<int>>, vector<vector<int>>> Graph::floydWarshall() {
87
    vector<vector<int>> dist = adjMatrix;
88
    vector<vector<int>> next(n, vector<int>(n, -1));
89
    // 初始化 next 矩阵：若存在直接边则 next[i][j] = j
90
    for (int i = 0; i < n; ++i) {
91
        for (int j = 0; j < n; ++j) {
92
            if (dist[i][j] != INT_MAX && i != j) {
93
                next[i][j] = j;
94
            }
95
        }
96
    }
97
    // 三层循环，动态规划
98
    for (int k = 0; k < n; ++k) {
99
        for (int i = 0; i < n; ++i) {
100
            for (int j = 0; j < n; ++j) {
101
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
102
                    dist[i][k] + dist[k][j] < dist[i][j]) {
103
                    dist[i][j] = dist[i][k] + dist[k][j];
104
                    next[i][j] = next[i][k];
105
                }
106
            }
107
        }
108
    }
109
    return {dist, next};
110
}
111

112
// 使用 prev 数组重建路径（Dijkstra）
113
// 从 target 回溯到 source，如果回溯后首节点不是 source 则说明无路径
114
vector<int> Graph::getPath(int source, int target, const vector<int>& prev) {
115
    vector<int> path;
116
    for (int at = target; at != -1; at = prev[at]) {
117
        path.push_back(at);
118
    }
119
    reverse(path.begin(), path.end());
120
    if (!path.empty() && path[0] == source) return path;
121
    return {};
122
}
123

124
// 使用 Floyd-Warshall 的 next 矩阵重建路径
125
vector<int> Graph::getPathFW(int source, int target, const vector<vector<int>>& next) {
126
    if (next[source][target] == -1) return {};
127
    vector<int> path = {source};
128
    while (source != target) {
129
        source = next[source][target];
130
        path.push_back(source);
131
    }
132
    return path;
133
}