前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >单源最短路径 Dijkstra算法 Java 代码实现(贪心算法)

单源最短路径 Dijkstra算法 Java 代码实现(贪心算法)

原创
作者头像
ruochen
修改2021-05-17 10:20:38
1.4K0
修改2021-05-17 10:20:38
举报

单元最短路径

问题分析

Java 源代码

内含详细注释

代码语言:txt
复制
package Dijkstra;

public class Dijkstra {

	public static void main(String[] args) {
		float max = Float.MAX_VALUE;
		float[][] a = new float[][] {{0, 0, 0, 0, 0, 0},
							{0, max, 10, max, 30, 100},
							{0, max, max, 60, max, max},
							{0, max, max, max, max, 20},
							{0, max, max, 10, max, 50},
							{0, max, max, max, max, max}};
		int v = 1;
		int n = 5;
		float[] dist = new float[n + 1];
		int[] prev = new int[n + 1];
		dijkstra(v, a, dist, prev);
		for (int i = 1; i <= n; i++) {
			if (i != v) {
				System.out.println(v + "->" + i + " : " + dist[i]);
			}
		}
	}
	
	/**
	 * 单元最短路径问题的 Dijkstra 算法 
	 * @param v: 源顶点
	 * @param a:邻接矩阵
	 * @param dist:存放最短路径
	 * @param prev:存放当前顶点的前一个顶点
	 */
	public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) {
		
		int n = dist.length - 1;
		if (v < 1 || v > n) return;
		// 代表当前顶点是否被添加到集合S中
		boolean[] s = new boolean[n + 1];
		// 初始化
		for (int i = 1; i <= n; i++) {
			dist[i] = a[v][i];
			s[i] = false;
			if (dist[i] == Float.MAX_VALUE) prev[i] = 0;
			else prev[i] = v;
		}
		dist[v] = 0;
		s[v] = true;
		for (int i = 1; i < n; i++) {
			float temp = Float.MAX_VALUE;
			int u = v;
			for (int j = 1; j <= n; j++) {  // 寻找不在S中的最小值
				if (!s[j] && (dist[j] < temp)) {  // 从剩余顶点选择
					u = j;
					temp = dist[j];
				}
			}
			// 加入s中
			s[u] = true;
			for (int j = 1; j <= n; j++) {  // 更新dist
				if ((!s[j]) && (a[u][j] < Float.MAX_VALUE)){
					float newdist = dist[u] + a[u][j];
					if (newdist < dist[j]) {
						dist[j] = newdist;
						prev[j] = u;
					}
				}
			}
		}
	}
}
代码语言:txt
复制
1->2 : 10.0
代码语言:txt
复制
1->3 : 40.0
代码语言:txt
复制
1->4 : 30.0
代码语言:txt
复制
1->5 : 60.0

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 单元最短路径
    • 问题分析
      • Java 源代码
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档