【笔记】数据结构与算法之Dijkstra（最短路）

QingYi.

第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
所有边权均为正值，请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

[Java] 纯文本查看 复制代码

import java.util.Scanner;
/*


适用于稠密的边

 */


public class Main {
    private static int N= 510;
    static int n,m;
    //为稠密阵所以用邻接矩阵存储
    static int[][] g = new int[N][N];
    // distance 距离
    static int [] dist = new int[N];
    //statue  判断当前的点是不是最终确定的最短点
    static  boolean [] st = new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //首先把每个点设置无限大
                g[i][j] = 0x3f3f3f;
            }
        }
        while (m-- >0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            // 如果重边了 保留最短的那条
            g[x][y] = Math.min(g[x][y],z);
        }
        System.out.println(dijkstra());
    }

    private static int dijkstra() {
        //初始化
        for (int i = 0; i < N; i++) {
            dist[i] = 0x3f3f3f;
        }
        // 第一个点到自己的距离是0
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
//           由于每一次都要找到还没有确定最短路距离的所有点中，距离当前的点最短的点。
//           t = - 1是为了在st这个集合中找第一个点更新时候的方便所设定的。
            int t = -1;
            for(int j = 1;j<=n;j++){
                //当前的j没有用过  如果t是-1的话 或者dt > dj  t就等于j
                if (!st[j] && (t==-1 || dist[t]>dist[j])){
                    t = j;
                }
            }
            if (t==n){
                break;
            }
            st[t] = true;
            //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
            for(int j = 1;j<=n;j++){
                dist[j] = Math.min(dist[j],dist[t]+g[t][j]);
            }
        }
        if(dist[n]==0x3f3f3f)  return -1;
        return dist[n];
    }
}

QingYi.

终于考试完考察完了，抽空学习一下

REK_滑稽

收藏一下，有空就学习一下，

云柔猫猫

收藏一下，有空学习

叫不醒装睡的人

感谢楼主分享