当前位置：首页 > article >正文

Java数据结构之《最短路径》(难度系数100)

article 2024/11/17 16:36:39

一、前言：

这是怀化学院的：Java数据结构中的一道难度偏难(偏难理解)的一道编程题(此方法为博主自己研究，问题基本解决，若有bug欢迎下方评论提出意见，我会第一时间改进代码，谢谢！) 后面其他编程题只要我写完，并成功实现，会陆续更新，记得三连哈哈! 所有答案供参考，不是标准答案，是博主自己研究的写法。(这一个题书上也有现成类似的代码，重要的是理解它的算法原理!)

二、题目要求如下：

(第 10 题) 最短路径(难度系数100)

最短路径
描述：
已知一个城市的交通路线，经常要求从某一点出发到各地方的最短路径。例如有如下交通图：

则从A出发到各点的最短路径分别为：
B：0
C：10
D：50
E：30
F：60
输入：
输入只有一个用例，第一行包括若干个字符，分别表示各顶点的名称，接下来是一个非负的整数方阵，方阵维数等于顶点数，其中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

三、代码实现： (代码的做题原理全部在代码注释中，若还有疑问也可以翻数据结构书关于快速排序的基本原理的内容)

补充：这个题我是基于邻接矩阵实现有向图的最短路径搜索。应该当你放到考试系统里检测代码是否正确时，请把所有的代码注释去掉！不过是自己的编译器应该没问题的。

(1)为了方便我全部将操作的方法和输入输出全部放在一个类:Main类里。在书上是分开去写，这样看的清楚一点，好理解一点，用的时候只要实例化对象调用方法就行。

package com.fs.graph;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String vertex= sc.next();  //输入记录所有顶点的字符串
        int len=vertex.length();
        int[][]edges = new int[len][len];  //有向图的关系矩阵
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                edges[i][j]=sc.nextInt();
            }
        }
        //这里的作用就是把所有关系矩阵中的某个值为0的数：给它赋值成(最大值一个 int可以有2的31次方 -1)意思代表它与某个顶点无边的意思(可以这样表示：无穷->无边)
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(edges[i][j]==0){
                    edges[i][j]=Integer.MAX_VALUE;
                }
            }
        }
        //输入出发顶点：那就要找到源点(也就是出发点)在字符串的位置，因为要从这个地方的下标去关系矩阵找它到其他顶点的最短路径
        int v=vertex.indexOf(sc.next());
        //标记出发点到该顶点是否已经找到了最短路径，如果是(true:表示已经找到，反之表示没有)
        //当前创建的时候全部默认是false
        boolean[] st =new boolean[len];
        //用来储存出发点到各个顶点的最短路径长度(当然出发点到出发点为0)
        int [] distance = new int[len];
        for(int i=0;i<len;i++){
            distance[i]=edges[v][i];  //这里就是初始的时候出发点到各个顶点的最短路径长度
        }
        st[v]=true;  //给它自己到自己的最短路径已经找到，并标记true
        //现在开始寻找
        for(int i=0;i<len;i++){
            //设置默认路径最小值为"无穷"
            int min = Integer.MAX_VALUE;
            //默认每次寻找到的顶点的最小路径的下标
            int index=-1;
            for(int j=0;j<len;j++){
                //条件是要去没有找到最短路径的顶点中去寻找
                if(st[j]==false){
                    //因为之前已经把所有最初的：出发点到各个顶点的暂时最段路径记下
                    //所以依次去寻找出发点到各个顶点中：相互比较后第一个最小距离的下标
                    if (distance[j] < min) {
                        index = j;  //每找到一个就把索引变化
                        min = distance[j];
                    }
                }

            }
            //循环结束后：如果找到出发点到索引index顶点的最短路径长度
            if(index!=-1) {
                st[index] = true;
            }else{
                //表示全都其余顶点都与出发点的边都没关系
                break;
            }
            //接下来就要分析前面得到的最短路径是否是真的最短
            //因为有两种情况(1.出发点只能直接到这个顶点的距离，不能经过某个其他的点再到这个顶点 2.还有就是它能够通过出发点到其他点再到现在这个点)
            //就是比较这两个哪个路径最短
            for(int k=0;k<len;k++){
                //首先要判断这个顶点是否已经找到最短路径了
                if(st[k]==false){
                    //要求已经找到最短路径的这个顶点能够通过存在的边到达某个其余顶点
                    //而且当已经找到最短路径的这个顶点(也就是从出发点到这个顶点最短路径)+这个顶点到某个其余顶点的距离：如果小于出发点直接到达某个顶点的距离(也就是最开始设定的"最短路径"，不经过其他顶点)
                    if(((edges[index][k])!=Integer.MAX_VALUE)&&(min+edges[index][k]<distance[k])){
                        distance[k]=min+edges[index][k];  //满足就要更新一次最短路径
                    }
                }
            }

        }
        //最后打印出发点到各个顶点间的最短路径
        for(int i =0;i<len;i++){
            if(i==v)continue;  //出发点题目不要求输出
            //如果没有路径可走也就是输出0 ，因为之前全部把0变成最大值，所以现在要变回来0
            if(distance[i]==Integer.MAX_VALUE){
                distance[i]=0;
            }
            System.out.println(vertex.charAt(i)+": "+distance[i]);
        }
    }

}

四、代码测试运行结果：

<1>题目上的测试输入样例：