当前位置：首页 > ds >正文

c++算法学习6——迪杰斯特拉算法

ds 2025/7/15 11:33:54

一、题目：城市交通最短路径规划

问题描述

某城市有N个交通节点（编号1~N）和M条单向道路。每条道路连接两个节点，并有一个长度值表示通过该道路的时间消耗。现需要计算从中央车站（节点1）到其他所有节点的最短通行时间。

输入格式

第一行：两个整数N和M，表示节点数和道路数
接下来M行：每行三个整数X, Y, D，表示从节点X到节点Y有一条长度为D的单向道路
数据范围：1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 道路长度D为正整数

输出格式

一行N个整数：表示从节点1到每个节点的最短时间，不可达输出-1

输入样例

输出样例

0 2 7 5 9 15

二、迪杰斯特拉算法详解

2.1算法核心思想

迪杰斯特拉算法是一种解决单源最短路径问题的经典算法，由荷兰计算机科学家Edsger Dijkstra于1956年提出。它采用贪心策略，逐步确定从源点到其他所有顶点的最短路径。

2.2算法特点：

适用于有向图或无向图
要求边权值非负
时间复杂度取决于实现方式（O(N²)或O(MlogN)

2.3算法执行步骤

初始化：
- 创建距离数组dist[]，存储源点到各点的最短距离
- 创建访问标记数组visited[]，记录节点是否已处理
- 设置源点距离为0，其他点为无穷大(INT_MAX)
主循环（执行N-1次）：
a. 选择当前距离最小且未访问的节点
b. 标记该节点为已访问
c. 更新该节点邻居的距离值
输出结果：dist[]数组即为所求
执行步骤图：

三、邻接矩阵实现（适合稠密图）

#include <iostream>
#include <climits>
using namespace std;const int MAXN = 105;
const int INF = INT_MAX;int N, M;
int graph[MAXN][MAXN]; // 邻接矩阵存储图
int dist[MAXN];        // 存储最短距离
bool visited[MAXN];    // 访问标记数组void dijkstra(int start) {// 初始化距离数组和访问数组for (int i = 1; i <= N; i++) {dist[i] = graph[start][i];visited[i] = false;}dist[start] = 0;visited[start] = true;// 进行N-1次循环for (int count = 1; count < N; count++) {int minDist = INF;int u = -1;// 选择当前距离最小的未访问节点for (int i = 1; i <= N; i++) {if (!visited[i] && dist[i] < minDist) {minDist = dist[i];u = i;}}if (u == -1) break; // 所有可达节点已处理visited[u] = true; // 标记为已访问// 更新u的邻居节点距离for (int v = 1; v <= N; v++) {if (!visited[v] && graph[u][v] != INF) {if (dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}}
}int main() {cin >> N >> M;// 初始化邻接矩阵for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {graph[i][j] = (i == j) ? 0 : INF;}}// 读入边for (int i = 0; i < M; i++) {int x, y, d;cin >> x >> y >> d;graph[x][y] = d;}dijkstra(1); // 从节点1开始// 输出结果for (int i = 1; i <= N; i++) {if (dist[i] == INF) cout << "-1 ";else cout << dist[i] << " ";}return 0;
}

四、算法优化：优先队列实现（适合稀疏图）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;typedef pair<int, int> pii; // first: 距离, second: 节点const int MAXN = 100005;
const int INF = INT_MAX;vector<pii> graph[MAXN]; // 邻接表
int dist[MAXN];
int N, M;void dijkstra(int start) {// 初始化距离数组for (int i = 1; i <= N; i++) {dist[i] = INF;}dist[start] = 0;// 小顶堆优先队列priority_queue<pii, vector<pii>, greater<pii>> pq;pq.push({0, start});while (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();// 跳过已处理的旧数据if (d != dist[u]) continue;// 遍历邻居节点for (auto &edge : graph[u]) {int v = edge.first;int w = edge.second;// 松弛操作if (dist[u] + w < dist[v]) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}
}int main() {cin >> N >> M;// 构建邻接表for (int i = 0; i < M; i++) {int x, y, d;cin >> x >> y >> d;graph[x].push_back({y, d});}dijkstra(1);// 输出结果for (int i = 1; i <= N; i++) {if (dist[i] == INF) cout << "-1 ";else cout << dist[i] << " ";}return 0;
}

五、算法应用场景

网络路由：路由器计算最短路径
交通导航：GPS系统计算最快路线
社交网络：计算人际关系最短路径
游戏AI：寻路算法实现
物流规划：货物配送路径优化

六、算法变种与应用

1. 最小花费问题（带权值转换）

// 在松弛操作中修改更新公式：
dist[v] = min(dist[v], dist[u] * (1 - fee) + cost);

2. 多源BFS（分糖果问题）

void bfs(int start) {queue<int> q;q.push(start);dist[start] = 1;while (!q.empty()) {int u = q.front(); q.pop();for (int v : graph[u]) {if (dist[v] > dist[u] + 1) {dist[v] = dist[u] + 1;q.push(v);}}}
}