迪杰斯特拉

2021/7/23 23:21:18

本文主要是介绍迪杰斯特拉,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

做关于求最短路径问题时有三种基本算法

这里分享一种(迪杰斯特拉算法)

void djs() {
	for (int i = 1; i <= n - 1; i++) {
		mix = INF;//每次让mix最大  方便下一次找最小值
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && dis[j] < mix) {//当j未被访问 j的最短距离小于mix(及j是存在的点)
				u = j;//记录j的坐标
				mix = dis[j];//记录j的长度  也方便找出最短路
			}
		}//循环结束后可找到当前点到相邻距离最短的点
		vis[u] = 1;//标记访问
		for (int j = 1; j <= n; j++) {
			if (map[u][j] < INF) {//找最小点到他可到达的点  如果找到进行判断
				if (dis[u] + map[u][j] < dis[j]) {//当前点u加上他到j这个点的距离小于 起点到j点的距离时  更新到j的最短距离
					dis[j] = dis[u] + map[u][j];
				}
			}
		}
	}
}



这篇关于迪杰斯特拉的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程