dijstra算法——单元最短路径算法

server/2024/10/20 10:14:21/

Dijkstra算法

用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。Dijkstra的时间复杂度是O(n^2)，它不能处理存在负边权的情况。

算法描述：

设起点为s，dis[v1表示从s到v的最短路径长度

(1).初始化：dis[v]=(vs)；dis[s]=0

(2).for (i = 1;i<= n ；i++)

1.在没有被访问过的点中找一个顶点u使得dis[ul是最小的。

2.u标记为已确定最短路径

3.for与u相连的每个未确定最短路径的顶点v

if (dis[u]+w[u][v] < dis[v])
{dis[v] = dis[u] + w[u][v]；
}

(3)算法结束：dis[v]为s到v的最短距离；

在这里插入图片描述
我们来看个例子：

我们来做到题练习一下：https://acm.hdu.edu.cn/showproblem.php?pid=2544

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;#define INF 0x3f3f3f3f // 定义一个代表无穷大的常量
const int M = 1e4 + 10; // 最大边数
const int N = 1e3 + 10; // 最大节点数int n, m; // n为节点数，m为边数
int mp[N][N]; // 图的邻接矩阵
int dis[N]; // 存储最短路径的数组
bool vis[N]; // 存储每个节点是否被访问的数组void initmp()
{memset(mp, INF, sizeof(mp));
}void dijkstra(int s) {memset(vis, 0, sizeof(vis)); // 初始化访问数组，0表示未访问，1表示已访问memset(dis, 0x3f, sizeof(dis)); // 初始化最短路径数组为无穷大dis[s] = 0; // 起始点到自身的距离为0while (1) {int mini = 0, min_ = INF; // 用于记录当前最小距离的节点for (int j = 1; j <= n; j++) {// 找到未访问的节点中距离起始点最近的节点if (!vis[j] && min_ > dis[j]) {mini = j;min_ = dis[j];}}// 如果没有找到未访问的节点，说明结束if (mini == 0) {break;}vis[mini] = 1; // 将当前节点标记为已访问for (int i = 1; i <= n; i++) {// 如果节点i未访问且通过mini节点到达i的距离小于当前已知的距离，则更新距离if (!vis[i] && dis[i] > dis[mini] + mp[mini][i]) {dis[i] = dis[mini] + mp[mini][i];}}}
}int main() {// 初始化邻接矩阵为无穷大memset(mp, INF, sizeof(mp));while (scanf("%d%d", &n, &m) != EOF && n) { // 读取节点数和边数，直到n为0initmp();// 读取边的信息for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;// 更新邻接矩阵，取最小边权if (mp[u][v] > w) {mp[u][v] = mp[v][u] = w;}}dijkstra(1); // 从节点1开始计算最短路径cout << dis[n] << endl; // 输出从节点1到节点n的最短路径}return 0;
}