JoshuaLi

用户名：dotcpp0615377

访问量：1340

签　名：

等　　级
排　　名	29603
经　　验	514
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业

　　自我简介：

TA的其他文章

模板题Dijkstra (JAVA)
浏览：60

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

A+B for Input-Output Practice （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

模板题Dijkstra (JAVA)

　　作者: JoshuaLi　　　　发表时间：2023-05-25 00:08:29 浏览：60　|　评论：0　

原题链接：城市路(Dijkstra)

```java
import java.util.Scanner;

public class Dijkstra最短路 {
	static final int max = 10000;

public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] matrix = new int[n+1][n+1];

for (int i = 0; i < matrix.length; i++) 
			for (int j = 0; j < matrix.length; j++) 
				matrix[i][j] = max;
		
		for (int i = 0; i < m; i++) {
			int source = sc.nextInt();
			int target = sc.nextInt();
			int weight = sc.nextInt();
			if(matrix[source][target] > weight)
				matrix[source][target] = weight;
			if(matrix[target][source] > weight)
				matrix[target][source] = weight;
		}
			
		dijkstra(matrix, 1);
		
	}
	
	 static void dijkstra(int[][] matrix,int source){
		int[] shortest = new int[matrix.length];
		int[] visied = new int[matrix.length];
		String[] path = new String[matrix.length];
		
		for (int i = 0; i < path.length; i++) {
			path[i] = new String(source +"->" + i);
		}
		
		shortest[source] = 0;
		visied[source] = 1;
		
		for (int i = 1; i < matrix.length; i++) {
			int min = Integer.MAX_VALUE , index = -1;
			
			for (int j = 0; j < matrix.length; j++) {
				if(visied[j] == 0 && matrix[source][j] < min) {
					min = matrix[source][j];
					index = j;
				}
			}
			shortest[index] = min;
			visied[index] = 1;
			
			for (int j = 0; j < matrix.length; j++) {
				if(visied[j] == 0 && matrix[source][j] > matrix[source][index] + matrix[index][j] ) {
					matrix[source][j] = matrix[source][index] + matrix[index][j];
					path[j] = path[index] + "->" + j;
				}
			}
			
		}
		
//		for (int i = 0; i < matrix.length; i++) {
//			if(shortest[i] != max)
//				System.out.println(path[i]+"="+matrix[source][i]);
//		}
		System.out.println(shortest[matrix.length-1]);
	}

}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JoshuaLi

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

A+B for Input-Output Practice （C语言代码）

分糖果（C语言代码）

C二级辅导-进制转换（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

模板题Dijkstra (JAVA)

评论区

精彩推荐

C二级辅导-温度转换（C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

时间转换（Java代码）

A+B for Input-Output Practice （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

DNA （C语言描述，数据结构）

printf基础练习2 （C语言代码）

有关字符，字符串的输入输出函数说明

Tom数（C语言代码）

JoshuaLi

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

A+B for Input-Output Practice （C语言代码）

分糖果 （C语言代码）

C二级辅导-进制转换 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

模板题Dijkstra (JAVA)

评论区

精彩推荐

C二级辅导-温度转换 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

时间转换 （Java代码）

A+B for Input-Output Practice （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

DNA （C语言描述，数据结构）

printf基础练习2 （C语言代码）

有关字符，字符串的输入输出函数说明

Tom数 （C语言代码）

分糖果（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

C二级辅导-温度转换（C语言代码）

时间转换（Java代码）

Tom数（C语言代码）