Java教程

迪杰斯特拉

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

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

这里分享一种（迪杰斯特拉算法）

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];
				}
			}
		}
	}
}

这篇关于迪杰斯特拉的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航