Dijkstra算法

迪杰斯特拉算法

算法介绍
Dijkstra 算法 是经典的 最短路径算法，用于计算从一个源顶点到图中其他所有顶点的最短路径。它的核心思想是从起始顶点开始，逐步“扩展”到其他顶点，每次选择距离起始顶点最近的未处理顶点，从而逐步找到最短路径。Dijkstra 算法本质上是基于 贪心算法 的思想，优先选择当前最短的路径。

算法过程

1. 初始化
   假设我们以顶点 $v$ 作为起始点，图中的顶点集合为 $V = { v_1, v_2, \cdots, v_n }$。
   初始化一个距离集合 $Dis = { d_1, d_2, \cdots, d_n}$，其中 $d_i$ 表示从起点 $v$ 到顶点 $v_i$ 的当前最短距离。
   • 对于起点 $v$，距离为 0，即 $d_v = 0$；
   • 对于其他顶点，初始距离设置为无穷大（表示还未找到路径）。
     初始时，所有顶点都没有被访问过，所有的距离值都存储在集合 $Dis$ 中。
2. 选择当前最短的顶点
   从距离集合 $Dis$ 中选择当前距离最小的顶点 $v_i$，并将其从 $Dis$ 集合中移除。
   此时，$v$ 到 $v_i$ 的路径就是最短路径。
3. 更新邻接顶点的距离
   以 $v_i$ 为中心，更新从 $v$ 到其他尚未访问顶点的距离。
   对于每个未访问的邻接顶点 $v_j$，我们需要比较：
   • 从 $v$ 直接到 $v_j$ 的距离（即$dis[v_j]$）；
   • 从 $v$ 经由 $v_i$ 到 $v_j$ 的距离（即 $dis[v_i] + \text{weight}[v_i][v_j]$）。
     如果通过 $v_i$ 的路径更短，就更新 $Dis$ 中对应的距离，并且更新 $v_j$ 的前驱节点为 $v_i$，表示通过 $v_i$ 到达 $v_j$。
4. 重复步骤 2 和 3
   重复执行步骤 2 和步骤 3，直到所有顶点都被访问过，或者找到了目标顶点的最短路径。
5. 终止条件
   当所有顶点都被处理过时，或者当最短路径已经找到（即目标顶点的距离已经确定），算法结束。

思路总结：

Dijkstra 算法通过**逐步“扩展”**最短路径来寻找从源顶点到其他顶点的最短路径。它的核心思想是：每次选择当前已知的最短路径，更新其邻接顶点的路径，并通过不断重复这一过程，最终得到从起点到所有其他顶点的最短路径。

题目：

求G点到其余各点的最短路径（后一版代码可以更进一步求出具体路径是什么）

代码实现(简洁版)

DijkstraAlgorithm

import java.util.Arrays;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        // 顶点数组，表示图中的7个顶点
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        
        // 无限大表示没有连接的边
        final int N = 65535;
        
        // 邻接矩阵表示图，0表示自己到自己，其他值表示两点之间的权重
        int[][] matrix = {
            // A   B   C   D   E   F   G
            {0,  10, 20, N,  N,  N,  N}, // A
            {10, 0,  N, 30, 50,  N,  N}, // B
            {20, N, 0,  N, 10,  N,  N}, // C
            {N, 30, N, 0,  N,  N, 60},  // D
            {N, 50, 10, N, 0,  20, N},  // E
            {N, N, N, N, 20, 0,  30},  // F
            {N, N, N, 60, N, 30, 0}    // G
        };
        
        // 选择源顶点
        int start = 0; // 从 A（索引 0）开始

        // 调用 Dijkstra 算法计算最短路径
        dijkstra(matrix, start, vertex.length);
    }

    /**
     * Dijkstra 算法实现
     * 
     * @param graph 邻接矩阵表示的图
     * @param start 起始节点的索引
     * @param vertexCount 顶点数量
     */
    public static void dijkstra(int[][] graph, int start, int vertexCount) {
        int[] dist = new int[vertexCount]; // dist[i]存储从start到i的最短路径
        boolean[] visited = new boolean[vertexCount]; // visited[i]表示i节点是否已访问

        // 初始化：所有距离为无穷大，起始节点的距离为0
        Arrays.fill(dist, 65535); 
        dist[start] = 0;

        for (int i = 0; i < vertexCount; i++) {
            // 选择未访问的节点中距离起点最小的节点
            int u = -1;
            int minDist = 65535;
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }

            // 如果所有节点都已访问，退出循环
            if (u == -1) {
                break;
            }

            // 标记当前节点已访问
            visited[u] = true;

            // 更新与当前节点相邻节点的距离
            for (int v = 0; v < vertexCount; v++) {
                // 如果从u到v有路径且v节点未访问过
                if (graph[u][v] != 65535 && !visited[v]) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist; // 更新最短路径
                    }
                }
            }
        }

        // 打印从起始节点到其他节点的最短路径
        System.out.println("从 " + (char)('A' + start) + " 出发的最短路径：");
        for (int i = 0; i < vertexCount; i++) {
            if (dist[i] == 65535) {
                System.out.println((char)('A' + i) + " 不可达");
            } else {
                System.out.println((char)('A' + i) + " 的最短路径长度为: " + dist[i]);
            }
        }
    }
}

代码实现(封装)

DijkstraAlgorithm

package com.yukinoshita.algorithm.dijkstra;

import java.util.Arrays;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        final int N = 65535;
        int[][] matrix = {
                {0, 10, 20, N, N, N, N},
                {10, 0, N, 30, 50, N, N},
                {20, N, 0, N, 10, N, N},
                {N, 30, N, 0, N, N, 60},
                {N, 50, 10, N, 0, 20, N},
                {N, N, N, N, 20, 0, 30},
                {N, N, N, 60, N, 30, 0}
        };
        Graph graph = new Graph(vertex, matrix);
//        graph.showGraph();
        graph.dijkstra(6);

        graph.showResult();
    }
}

class Graph {
    private char[] vertex;//顶点数组
    private int[][] matrix;//邻接矩阵
    //里面有三个表：1. 记录已访问过节点的表；2. 前驱节点的下标；3. 已访问的节点到其余节点的距离
    private VisitedVertex vis;

    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void showGraph() {
        for (int[] m : matrix) {
            System.out.println(Arrays.toString(m));
        }
    }

    /**
     * Dijkstra算法实现
     *
     * @param index 开始顶点（起点）
     */
    public void dijkstra(int index) {
        vis = new VisitedVertex(vertex.length, index);
        update(index);

        for (int j = 1; j < vertex.length; j++) {
            index = vis.updateArr(); //选择新的访问顶点
            update(index);
        }
    }

    //更新加入index节点后 的 vis（每一个顶点对应前一个顶点的下标、访问过的顶点到其余顶点的距离）
    private void update(int index) {
        int len = 0;
        for (int j = 0; j < matrix[index].length; j++) {
            //len = 出发顶点到index的距离 + index到j的距离
            len = vis.getDis(index) + matrix[index][j];
            if (!vis.isVisited(j) && len < vis.getDis(j)) {
                vis.updatePre(j, index);//更新j的前驱为j
                vis.updateDis(j, len);//更新出发节点到j的距离为len
            }
        }
    }

    //显示结果：
    public void showResult() {
        System.out.println("所有顶点是否都已访问过?visted[]为:"+Arrays.toString(vis.visited));

        int start = 0;
        for (int i = 0; i < vis.dis.length; i++) {
            if (vis.dis[i] == 0) {
                start = i;
                break;
            }
        }
        System.out.println("起点" + vertex[start] + "到其余顶点的最短距离为：");
        for (int i = 0; i < vertex.length; i++) {
            System.out.println(vertex[start] + "->" + vertex[i] + "(" + vis.dis[i] + ")");
        }

        System.out.println("每个顶点的前驱顶点为：");
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i] != vertex[vis.preVisited[i]]) {
                System.out.println(vertex[i] + "的pre是" + vertex[vis.preVisited[i]]);
            } else {
                System.out.println(vertex[i] + "是起始点");
            }
        }
    }

}

class VisitedVertex {
    //记录各个顶点是否被访问过（1访问过，0未访问）
    public int[] visited;
    //每一个点对应的前一个顶点的下标
    public int[] preVisited;
    //记录已访问过的节点到其余节点的距离
    public int[] dis;

    /**
     * @param vertexNums 顶点个数
     * @param index      出发节点下标
     */
    public VisitedVertex(int vertexNums, int index) {
        this.visited = new int[vertexNums];
        this.preVisited = new int[vertexNums];
        this.dis = new int[vertexNums];
        Arrays.fill(dis, 65535);
        dis[index] = 0;
        visited[index] = 1;
        for (int i = 0; i < preVisited.length; i++) {
            preVisited[i] = i;//初始化每个顶点的前驱为自己（也就是没有前驱）
        }
    }

    public boolean isVisited(int index) {
        return visited[index] == 1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     *
     * @param index
     * @param len
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 更新前驱pre顶点的前驱为index
     *
     * @param pre
     * @param index
     */
    public void updatePre(int pre, int index) {
        preVisited[pre] = index;
    }

    /**
     * 返回出发顶点到index顶点的距离
     *
     * @param index
     * @return
     */
    public int getDis(int index) {
        return dis[index];
    }

    //继续选择并返回 下一个 访问结点
    public int updateArr() {
        int minLen = 65535, index = 0;
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == 0 && dis[i] < minLen) {
                minLen = dis[i];
                index = i;
            }
        }
        visited[index] = 1;//更新这个节点被访问过
        return index;
    }

}