7-2 Dijkstra算法（模板） (30分)

给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。 输入格式: 第一行四个由空格隔开的整数 n、m、s、t。 之后的 m 行，每行三个正整数 s​i​​、t​i​​、w​i​​(1≤w​i​​≤10​9​​)，表示一条从s​i​​ 到 t​i​​ 长度为 w​i​​ 的边。 输出格式: 一个整数，表示从s 到t 的最短路径长度。数据保证至少存在一条道路。 输入样例: 7 11 5 4 2 4 2 1 4 3 7 2 2 3 4 3 5 7 5 7 3 3 6 1 1 6 3 4 2 4 3 5 6 3 7 2 1

输出样例: 7

注意: 两个顶点之间可能存在多条直接相连的道路。

思路

纵观此题，要注意的点有两个——一是两个顶点之间可能存在多条直接相连的道路；二是数据保证至少存在一条道路。这意味此图必是稠密图，每两个顶点之间都有一条及以上的道路。据此我们可以用矩阵来存储此图，不过与先前不同的是矩阵里的每个元素应是我们自己定义的一个类，但是此题只需算出最短路径，那么这题我们路径只需保留最短的即可。

程序框架设计

1.array矩阵表示图，num结点数量，edge边数，maxInt常量表示无穷大，distance矩阵记录各个点之间的最短距离，s起点，t终点 2.initialize方法初始化图 3.私有方法createEdge（int a,int b）方法 建立一条边，把最短的一条边记录 4.dijkstra()方法 5. findMinDistance(boolean[] collected) 返回未被收录顶点中dist最小者的下标 6.find(int t)输出打印到t点的最短距离

import java.util.*;


public class Main {
    //一个常量100000001表示无穷大
    final static int MaxInt=100000001;
    //节点个数
    static int num=0;
    //边数
    static int edge=0;
    //二维矩阵
    static int[][] array;
    static int[] distance;
    static int[] path;
    //起点
    static int s;
    //终点
    static int t;
    //建图模块
    public static void main(String[] args) {
        //初始化
        initialize();
        //调用dijkstra算法
        Dijkstra();
        //输出到t点的最短距离
        find(t);

    }
    public static void initialize(){
        //创建一个文本扫描器检测键盘输入
        Scanner scanner=new Scanner(System.in);

        num=scanner.nextInt();
        edge=scanner.nextInt();
        s= scanner.nextInt();
        t= scanner.nextInt();
        //注意这个下标并不是结点值，下标减一才是！！！
        array=new int[num][num];
        //初始化图中值
        for (int i=0;i<num;i++){
            for (int j=0;j<num;j++){
                array[i][j]=MaxInt;
            }
        }

        for (int i=0;i<edge;i++){
            creatEdge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt());
        }
        //初始化path和distance数组
        path=new int[num];
        distance=new int[num];

    }
    //建立一条边,把小的一条边存储
    private static void creatEdge(int a,int b,int length){
        if (array[a-1][b-1]>length){
            array[a-1][b-1]=length;
            array[b-1][a-1]=length;
        }
    }

    private static boolean Dijkstra()
    {
        //记录该点是否访问过
        boolean collected[]=new boolean[num];


        /* 初始化：此处默认邻接矩阵中不存在的边用MaxInt表示 */
        for ( int i=0; i<num; i++ ) {
            distance[i] = array[i][s-1];
            if ( distance[i]<MaxInt )
                path[i] = s-1;
            else
                path[i] = -1;
            collected[i] = false;
        }
        /* 先将起点收入集合 */
        distance[s-1] = 0;
        collected[s-1] = true;

        while (true) {
            // temp = 未被收录顶点中dist最小者的下标
            int temp= findMinDistance(collected );
            if ( temp==-1 ) /* 若这样的temp不存在 */
                break;      /* 算法结束 */
            collected[temp] = true;  /* 收录temp */
            for( int i=0; i<num; i++ ) /* 对图中的每个顶点i+1 */
                /* 若i是temp的邻接点并且未被收录 */
                if ( collected[i]==false && array[temp][i]<MaxInt ) {
                    if (array[temp][i]<0 ) /* 若有负边 */
                        return false; /* 不能正确解决，返回错误标记 */
                    /* 若收录temp使得distance[i]变小 */
                    if ( distance[temp]+array[temp][i]< distance[i] ) {
                        distance[i] = distance[temp]+array[temp][i]; /* 更新distance[i] */
                        path[i] = temp; /* 更新s到i的路径 */
                    }
                }
        } /* while结束*/
        return true; /* 算法执行完毕，返回正确标记 */
    }
    //返回未被收录顶点中dist最小者的下标
    private static int findMinDistance(boolean[] collected){
        int min =MaxInt;
        int iMin=-1;
        for (int i=0;i<num;i++){
            if (min>distance[i]&&!collected[i]){
                min=distance[i];
                iMin=i;
            }
        }
        return iMin;
    }
    //输出打印到t点的最短距离
    private static void find(int t){
        System.out.println(distance[t-1]);
    }


}

记录点滴，乐于分享，转载请注明出处 愿我们以梦为马，不负人生韶华。 我们追梦在路上！ 愿与君共勉！