课程学习--算法总结 图论算法(第4期)--最短路径--迪杰斯特拉(Dijkstra)Java描述

一、 概述
单源最短路径算法，从指定出发点到其他各个顶点的最短路径。

二、 相关参数

1. root 起始节点
2. visited[] 一维数组 记录节点是否访问
3. dist[] 一维数组 起点到各个节点的距离

三、 算法流程描述

1. 存图
2. 初始化参数
3. 遍历n次
4. 更新visited
5. 更新dist

四、 主要算法

1. 取小算法
2. 选择排序
3. 广度优先
4. 贪心思想

五、模板

package cn.charliejohn.graph.mp;

import java.util.Arrays;


public class NetworkDelayTime743 {

    
    final int SUP = Integer.MAX_VALUE >> 1;

    
    public int networkDelayTime(int[][] times, int n, int k) {
        // 图的邻接矩阵
        int[][] g = new int[n][n];

        // 存图
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], SUP);
        }
        for (int[] t : times) {
            int x = t[0] - 1;
            int y = t[1] - 1;
            g[x][y] = t[2];
        }

        // 每个顶点的距离
        int[] dist = new int[n];
        Arrays.fill(dist, SUP);

        // 起始节点
        dist[k - 1] = 0;

        // 顶点集合(未访问 : 0 ; 已访问 : 1)
        boolean[] used = new boolean[n];

        // 遍历n次
        for (int i = 0; i < n; ++i) {

            // 起始标志
            int x = -1;
            for (int y = 0; y < n; ++y) {
                // 没有访问过, 并且为起始, 或者不是起始, 距离较小的
                // 选择排序
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }

            // 更新used[], 第一次是起点
            used[x] = true;

            // 更新dist[]
            for (int y = 0; y < n; ++y) {
                // 起点到各点的距离, 不可达到就是SUP, 可达就是各个最短路径的累加
                dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
            }
        }

        int ans = Arrays.stream(dist).max().getAsInt();
        // 无法到达则返回 -1
        return ans == SUP ? -1 : ans;
    }
}