算法图文详解,已有大神讲解的十分清楚,请移步https://blog.csdn.net/qq_35644234/article/details/60870719

这里我主要看完别人思路,自己写一遍,加深理解;

附java代码和一些自己的理解.

public class Dijkstra {    private static int N = Integer.MAX_VALUE;    private static int[][] Graph = {            {N, 1, 5, N, N, N, N, N, N},            {
    1, N, 3, 7, 5, N, N, N, N},            {
    5, 3, N, N, 1, 7, N, N, N},            {N, 7, N, N, 2, N, 3, N, N},            {N, 5, 1, 2, N, 3, 6, 9, N},            {N, N, 7, N, 3, N, N, 5, N},            {N, N, N, 3, 6, N, N, 2, 7},            {N, N, N, N, 9, 5, 2, N, 4},            {N, N, N, N, N, N, 7, 4, N}};    /**     * 时间复杂度为O(N^2)     * 算法思想:一个节点到start节点的距离,有两种情况:     * (1)start直连距离(无连接,距离设为无穷大)     * (2)通过比直连距离短的节点中转(显然如果中转节点的路径长度比直连距离还短,就没必要从该节点中转)     * 第一步先执行(1),初始化各节点到start节点的直连距离,用数组记录     * 第二步执行(2)以直连距离最小的节点为中转,更新与中转节点连通的节点距离,更新数组     * (此步中,中转节点本身的路径已为最优,到中转节点的路径不可能从其他节点中转,原理见(2);     * 中转后变短的距离,可看成start节点到该节点拥有了一条更短的直连距离)     * 第三步,循环执行第二步确定其他N-2个节点的路径.     *     * @param start     * @param Graph     * @return     */    public static int[] dijkstra(int start,int[][] Graph){        int[] minDist = new int[Graph.length]; //start节点到各节点的距离        boolean[] findFlag = new boolean[Graph.length]; //标识节点是否找到最短路径        //初始化距离数组和标识数组        for (int i = 0; i < minDist.length; i++) {            minDist[i] = Graph[start][i];            findFlag[i] = false;        }        //初始化初始节点的距离和标识        minDist[start] = 0;        findFlag[start] = true;        //遍历其他节点,每次遍历确定一个节点的最短路径        for (int v = 1; v < Graph.length; v++) {            int temp = 0;  //记录中转节点索引            int min = N;  //记录start到中转节点的距离            for (int i = 0; i < minDist.length; i++) {                if(!findFlag[i] &&  minDist[i] < min){                    min = minDist[i];                    temp = i;                }            }            findFlag[temp] = true;            for (int i = 0; i < minDist.length; i++) {                //如果经过中转节点到i节点,比之前记录的路径要短,则更新路径                // 条件Graph[temp][i] != N不能少,否则后一项计算可能会溢出                if(!findFlag[i]&&Graph[temp][i] != N && minDist[i] > (min+Graph[temp][i])){                    minDist[i] = min + Graph[temp][i];                }            }        }        return minDist;    }    public static void main(String[] args) {        int[] res = dijkstra(0,Graph);        for (int i = 0; i < res.length; i++) {            System.out.print(res[i]+ " ");        }    }}