一、Dijkstra算法简介

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

二、Dijkstra算法思想

按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，保证：
（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 。
（反证法可证）
求最短路径步骤
算法步骤如下：
G={V,E}

1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
   若存在，d(V0,Vi)为弧上的权值
   若不存在，d(V0,Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
   重复上述步骤2、3，直到S 中包含所有顶点，即W=Vi为止

三、Dijkstra算法 Java代码

@Data
public class Dijkstra {
    // 距离矩阵
    double[][] distance;
    // 起点
    int start;
    // 终点
    int end;

    /**
     * @param distance
     * @param start
     * @param end
     * @Description 构造函数
     * @Author WSKH
     */
    public Dijkstra(double[][] distance, int start, int end) {
        this.distance = distance;
        this.start = start;
        this.end = end;
    }

    /**
     * @Description 进行求解
     * @Author WSKH
     */
    public void solve() {
        // 优先队列
        PriorityBlockingQueue<Node> priorityBlockingQueue = new PriorityBlockingQueue<>();
        // 加入初始点对应的临接点
        for (int i = 0; i < distance.length; i++) {
            if (i == start) {
                for (int j = 0; j < distance.length; j++) {
                    if (j != start) {
                        boolean[] booleans = new boolean[distance.length];
                        booleans[i] = true;
                        booleans[j] = true;
                        List<Integer> pathList = new ArrayList<>();
                        pathList.add(i);
                        pathList.add(j);
                        priorityBlockingQueue.add(new Node(new ArrayList<>(pathList), distance[i][j], booleans.clone(), j));
                    }
                }
                break;
            }
        }
        // 开始广度搜索
        while (!priorityBlockingQueue.isEmpty()) {
            Node node = priorityBlockingQueue.poll();
            System.out.println(node);
            // 如果当前节点是终点，那么直接输出最短路，程序结束
            if (node.getCurPointIndex() == end) {
                System.out.println("最短路为：" + node.getPathList());
                System.out.println("最短路长度为：" + node.getCurTotalPathLen());
                break;
            }

            // 如果当前节点不是终点，将当前节点的未激活的邻接顶点加入队列
            for (int i = 0; i < distance.length; i++) {
                if (!node.getBooleans()[i]) {
                    boolean[] clone = node.getBooleans().clone();
                    clone[i] = true;
                    ArrayList<Integer> list = new ArrayList<>(node.getPathList());
                    list.add(i);
                    priorityBlockingQueue.add(new Node(list, node.getCurTotalPathLen() + distance[node.getCurPointIndex()][i], clone, i));
                }
            }

        }
    }

    @Data
    @ToString
    @AllArgsConstructor
    class Node implements Comparable<Node> {
        // 路径索引
        List<Integer> pathList;
        // 当前节点总路径
        double curTotalPathLen;
        // 当前节点激活列表
        boolean[] booleans;
        // node对应的当前顶点索引
        int curPointIndex;

        @Override
        public int compareTo(Node o) {
            return Double.compare(curTotalPathLen, o.curTotalPathLen);
        }
    }
}

四、测试

public class Test {
    public static void main(String[] args) {
        double[][] distance = new double[][]{
                {0,6,13,20,10,9,3,4,4},
                {6,0,7,14,4,6,3,2,10},
                {13,7,0,9,11,13,10,9,17},
                {20,14,9,0,10,12,17,16,24},
                {10,4,11,10,0,2,7,6,14},
                {9,6,13,12,2,0,6,6,13},
                {3,3,10,17,7,6,0,1,7},
                {4,2,9,16,6,6,1,0,8},
                {4,10,17,24,14,13,7,8,0}
        };
        new Dijkstra(distance, 7, 4).solve();
    }
}

控制台输出如下：

Dijkstra.Node(pathList=[7, 6], curTotalPathLen=1.0, booleans=[false, false, false, false, false, false, true, true, false], curPointIndex=6)
Dijkstra.Node(pathList=[7, 1], curTotalPathLen=2.0, booleans=[false, true, false, false, false, false, false, true, false], curPointIndex=1)
Dijkstra.Node(pathList=[7, 0], curTotalPathLen=4.0, booleans=[true, false, false, false, false, false, false, true, false], curPointIndex=0)
Dijkstra.Node(pathList=[7, 6, 0], curTotalPathLen=4.0, booleans=[true, false, false, false, false, false, true, true, false], curPointIndex=0)
Dijkstra.Node(pathList=[7, 6, 1], curTotalPathLen=4.0, booleans=[false, true, false, false, false, false, true, true, false], curPointIndex=1)
Dijkstra.Node(pathList=[7, 1, 6], curTotalPathLen=5.0, booleans=[false, true, false, false, false, false, true, true, false], curPointIndex=6)
Dijkstra.Node(pathList=[7, 1, 4], curTotalPathLen=6.0, booleans=[false, true, false, false, true, false, false, true, false], curPointIndex=4)
最短路为：[7, 1, 4]
最短路长度为：6.0

[7, 1, 4]是指最短路径为7->1->4