当前位置: 首页 > article >正文

最短路径--dijkstra

文章目录

    • 最短路径的基本概念
    • dijsktra的算法思想
    • dijkstra的代码实现
    • dijkstra的堆优化
    • dijkstra的应用场景

最短路径的基本概念

1.路径长度:一条路径上所经过的边的数目
2.带权路径长度:路径上所经过边的权值之和
3.最短路径:带权路径长度值最小的那条路径
那么在一个图中,我们如果要求出起点到终点的最短路径,我们就需要用到最短路径算法。常见的最短路径算法有dijkstra,Floyd ,Ford,SPFA四种,我们这节仅介绍dijkstra算法。

dijsktra的算法思想

dijkstra算法的实质其实时不断更新dist数组的值(一个松弛的过程)来遍历图,最终得出起点到每一个点的最短路径长度。该算法基于贪心思想,初始时将起点到自己的距离设置为0,其它点都设置为无穷大,找到未被标记的dist数组中的最小值时,将其标记为1,再对该点的邻接点进行松弛操作重复即可。

dijkstra的代码实现

这里以邻接矩阵存储。

#include<iostream>
#define INF 10005
using namespace std;
int n, m;
int dist[105];//点i到起点的距离
int g[105][105];
int ans;
int vis[105];
int path[105];
void dijktra(int start) {
    vis[start] = 1;
	dist[start] = 0;
	path[start] = start;
	for (int i = 1;i <= n;i++) {
		if (g[start][i] < dist[i] && vis[i] == 0) {
           dist[i] = g[start][i];
		   path[i] = start;
		}
	}
	int t, minn;
	for (int j = 2;j <= n;j++) {
		minn = INF;
		t = -1;
		for (int i = 1;i <= n;i++) {
			if (minn > dist[i]&&vis[i]==0) {
				minn = dist[i];
				t = i;
			}
		}
		vis[t] = 1;
		for (int i = 1;i <= n;i++) {
			if (g[t][i]+dist[t] < dist[i] && vis[i] == 0) {
				dist[i] = g[t][i] + dist[t];
				path[i] = t;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			if (i != j) {
                g[i][j] = INF;
			}	
		}
	}
	int x, y, w;
	while (m--) {
		cin >> x >> y >> w;

		g[x][y] = g[y][x] = w;
	}
	cin >> x;
	dijktra(x);
	for (int i = 1;i <= n;i++) {
		printf("起点到%d的最短距离是%d,该路径为%d", i, dist[i],i);
		 int p = i;
		 while (path[p] != p) {
			 printf("%d ", p);
			 p = path[p];
		 }
		 printf("%d\n", p);

	}
	
	return 0;
}

dijkstra的堆优化

这里用到了c++ stl里面的优先队列的小顶堆,以链式前先星存储。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
int n, m,cnt;
int dis[105];
int vis[105];
int s;
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
struct edge {
	int to, next, w;
}e[10005];
void add(int x, int y, int w) {
	e[cnt].to = y;
	e[cnt].w = w;
	e[cnt].next = head[x];
	head[x] = cnt;
	cnt++;
}
void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({ 0,s });
	while (!q.empty()) {
		PII t = q.top();
		q.pop();
		int u = t.second,d=t.first;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = head[u]; i != -1; i = e[i].next) {
			int v = e[i].to;
			if (vis[v] == 0 && dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				q.push({ dis[v],v });
			}
		}
	}
}
int main() {
	cin >> n >> m>>s;
	int x, y, w;
	memset(head, -1, sizeof(head));
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> w;
		add(x, y, w);
	}
	dijkstra();
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
	return 0;
}

dijkstra的应用场景

该算法适用于边权非负的有向图和无向图,通常用于解决单源最短路径问题。


http://www.kler.cn/a/589403.html

相关文章:

  • Word 小黑第22套
  • 李宏毅NLP-1-课程介绍
  • 新能源汽车IGBT电压平台与SiC器件应用
  • 类和对象的创建
  • Python(1.1)Python实战:一键批量重命名图片文件,告别手动整理!(附完整源码)
  • python调用百度人脸识别接口
  • 【前端面试题】宏任务与微任务的区别
  • C语言之 循环语句:程序运行的核心动力(上)
  • vuex持久化存储,手动保存到localStorage
  • 奥林巴斯道Olympus DAO、奥拉丁模式、诺瓦银行、RWA模型合约解析开发
  • 大数据学习(70)-大数据调度工具对比
  • Navigation页面导航的使用
  • 基于javaweb的SpringBoot校园运动会管理系统设计与实现(源码+文档+部署讲解)
  • 6k ± 1 规则
  • 自然语言处理编程文档
  • 数组题型-二分查找-JS
  • 实战:自适应均衡的设计与实现
  • 【Docker】容器中安装cron命令
  • 使用 Docker 部署 MySQL 8
  • TensorFlow 基本原理与使用场景