网站怎么做好,建设施工合同备案在哪个网站,网站建设服务收费,宁德市人口最短路径 描述#xff1a; 已知一个城市的交通路线#xff0c;经常要求从某一点出发到各地方的最短路径。例如有如下交通图#xff1a; 则从A出发到各点的最短路径分别为#xff1a; B#xff1a;0 C#xff1a;10 D#xff1a;50 E#xff1a;30 F#xff1a;60 输… 最短路径 描述 已知一个城市的交通路线经常要求从某一点出发到各地方的最短路径。例如有如下交通图 则从A出发到各点的最短路径分别为 B0 C10 D50 E30 F60 输入 输入只有一个用例第一行包括若干个字符分别表示各顶点的名称接下来是一个非负的整数方阵方阵维数等于顶点数其中0表示没有路正整数表示两点之间边的长度。可以假定该图为有向图。 最后一行为要求的出发点。 输出 输出从已知起点到各顶点的最短路径长度。输出格式是根据顶点输入顺序依次输出其最智短路径长度。各顶点分别用一行输出先输出目标顶点然后一冒号加一个空格最后是路径长度。0表示没有路。 样例输入 ABCDEF 0 0 10 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0 A 样例输出 B: 0 C: 10 D: 50 E: 30 F: 60 方法一(Floyd算法)
import java.util.Scanner;public class Xingyuxingxi
{public static void main(String[] args){Scanner scnew Scanner(System.in);String strsc.next();int nstr.length();int [][]dtnew int[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {dt[i][j]sc.nextInt();if(dt[i][j]0i!j) {dt[i][j]5000000;//因为题目数据范围有限所以用5000000代替最大值也可以用别的数代替}}}char asc.next().charAt(0);for(int k0;kn;k){//floyd算法的简单之处只需要三层循环就能遍历出所有点到所有点的最短距离如果范围过大就不要用floyd算法了for(int i0;in;i){for(int j0;jn;j){dt[i][j]Math.min(dt[i][j],dt[i][k]dt[k][j]);//更新最短路径}}}int g0;for(int i0;in;i) {if(str.charAt(i)a) {//找到起始点的下标gi;break;}}for (int i 0; i n; i) {if(dt[g][i]5000000)dt[g][i]0;//如果为最大值表示没有路题目要求用0表示没有路if(str.charAt(i)!a)//如果不是起始点则输出最短距离System.out.printf(%c: %d\n,str.charAt(i),dt[g][i]);}}
}
方法二(Dijkstra算法)
import java.util.Scanner;public class Xingyuxingxi
{public static void main(String[] args){Scanner scnew Scanner(System.in);String strsc.next();int nstr.length();int [][]dtnew int[n][n];int []distnew int[n];//储存选定起点到其他点的距离boolean []stnew boolean[n];//储存该点是否遍历过到其他点的距离for (int i 0; i n; i) {for (int j 0; j n; j) {dt[i][j]sc.nextInt();if(dt[i][j]0i!j) {dt[i][j]5000000;//用5000000代替最大值Integer.MAX_VALUE}}}char asc.next().charAt(0);for (int i 0; i n; i) {dist[i]5000000;}int g0;for(int i0;in;i) {if(str.charAt(i)a){//找到起点下标gi;break;}}dist[g]0;for (int i 0; i n; i) {int t-1;for(int j0;jn;j) {if(!st[j](t-1||dist[t]dist[j])){//找到每次更新路线后t到起点的最短距离的点tj;}}st[t]true;for(int j0;jn;j){//更新距离,各个点到t的距离dist[j]Math.min(dist[j],dist[t]dt[t][j]);}}for (int i 0; i n; i) {if(dist[i]5000000)dist[i]0;//如果为最大值表示没有路题目要求用0代替没有通路if(i!g)System.out.printf(%c: %d\n,str.charAt(i),dist[i]);}}
} 关于为什么用5000000代替Integer.MAX_VALUE 因为题目中涉及到最大值的计算如果使用Integer.MAX_VALUE加任意一个数的话就会变为负数求最小值的话就会一直是Integer.MAX_VALUE其他数的和我自己写的时候每次加都会变成负数所以就把最大值改小了本题数据并不强可以用一个足够大的数代替这个最大值即可不一定非得是5000000
