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

C++基础算法：Dijkstra

ds 2025/5/5 6:23:46

1、概念

Dijkstra算法 是一种用于计算图中单源最短路径的算法，主要用于加权图（图中边的权重可以不同）中找出从起点到各个其他节点的最短路径。

Dijkstra算法的核心概念：

图的表示：

有向图：图的边是有方向的，表示从一个节点到另一个节点的路径。
加权图：图的每条边都有一个权重，表示通过该边的代价或距离。

最短路径：

计算从一个起点（源节点）到所有其他节点的最短路径，最短路径的定义是路径的权重之和最小。

贪心策略：

Dijkstra算法是一种贪心算法，即每次选择当前最短的路径扩展，不一定考虑全局的最优解，但局部选择最优后，最终能得到全局最优。

2、实战例子

给定n个点，m条边，求最后一个点的最短路径。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 1e5 + 10;
int w[N], e[N], ne[N], h[N]; // 边的权重、目标节点、邻接链表、每个节点的头指针
int dist[N], state[N]; // dist存储最短距离，state表示节点是否已处理
int idx = 0; // 当前边的索引
int n, m; // n为节点数，m为边数// 邻接表
void add(int a, int b, int c)
{e[idx] = b;     // 边的目标节点ne[idx] = h[a]; // 当前边指向的上一个节点的邻接边w[idx] = c;     // 边的权重h[a] = idx++;   // 更新节点a的邻接链表头为当前边的索引
}// Dijkstra算法的实现
void dijkstra()
{memset(dist, 0x3f3f3f3f, sizeof(dist)); // 初始化dist为无穷大dist[1] = 0; // 起点到自身的距离为0for (int i = 0; i < n; i++) {int t = -1;for (int j = 1; j <= n; j++) { // 找出未访问的距离最小的节点if(state[j] == 0 && (t == -1 || dist[j] < dist[t]))t = j;}state[t] = 1; // 标记节点t为已访问for (int k = h[t]; k != -1; k = ne[k]) { // 遍历t的所有邻接边int x = e[k]; // x是t的一个邻接节点dist[x] = min(dist[x], dist[t] + w[k]); // 更新dist[x]为更小的值}}
}int main()
{memset(h, -1, sizeof(h)); // 初始化所有节点的邻接链表头为-1cin >> n >> m; // 输入节点数n和边数mwhile (m--) {int x, y, z;cin >> x >> y >> z; // 输入每条边add(x, y, z); // 添加边}dijkstra(); // 运行Dijkstra算法if (dist[n] != 0x3f3f3f3f) // 如果到达节点n的最短距离不是无穷大，输出最短路径cout << dist[n];elsecout << -1; // 否则输出-1，表示无法到达节点nreturn 0;
}