实现 Dijkstra 算法

介绍

在本实验中，我们将使用 Java 实现 Dijkstra 算法。Dijkstra 算法是一种用于解决加权图最短路径问题的流行算法。

Skills Graph

创建 Graph 类

在这一步中，我们将创建一个名为 Graph 的类，用于表示我们的加权图。我们将在这个类中创建一个二维邻接矩阵来表示图的边。

class Graph
{
    int[][] adjMatrix; // 邻接矩阵，用于表示图的边
    int numOfvertices;

    Graph(int[][] mat, int v)
    {
        this.adjMatrix = mat;
        this.numOfvertices = v;
    }

    void addEdge(int src, int dest, int edgeWeight)
    {
        adjMatrix[src][dest] = edgeWeight;
        adjMatrix[dest][src] = edgeWeight;
    }
}

实现 Dijkstra 算法

在这一步中，我们将在 Java 中实现 Dijkstra 算法。我们将创建一个名为 getClosestVertex 的辅助方法，用于找到最近的未访问节点。我们还将在一个名为 dijkstrasShortestPath 的方法中实现主算法。该方法将接收一个 Graph 和一个源顶点作为参数，并返回最短距离数组。

public static int getClosestVertex(int[] distance, boolean[] visited) {
    int min = Integer.MAX_VALUE;
    int minIdx = -1;
    for(int i=0; i<distance.length; i++) {
        if(distance[i] < min)
            if(visited[i] == false) {
                min = distance[i];
                minIdx = i;
            }
    }
    return minIdx;
}

public static int[] dijkstrasShortestPath(Graph g, int src) {
    // 最终的最短距离数组
    int[] distance = new int[g.numOfvertices];
    // 用于标记顶点的最短距离是否已找到的数组
    boolean[] visited = new boolean[g.numOfvertices];

    // 初始化数组
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // 初始距离为无穷大
        visited[i] = false; // 任何节点的最短距离尚未找到
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // 获取最近的节点
        if(closestVertex == Integer.MAX_VALUE) // 如果最近的节点距离为无穷大，意味着无法到达其他节点，直接返回
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // 节点 j 的最短距离尚未确定
            {
                if(g.adjMatrix[closestVertex][j] != 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // 通过 closestVertex 的距离小于初始距离
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

测试我们的实现

在这一步中，我们将通过创建一个 main 方法来测试我们的实现。该方法会向图中添加边，并调用 dijkstrasShortestPath 方法来找到从源顶点到加权图中所有其他顶点的最短距离。

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // 向图中添加边
    graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);

    // 调用 Dijkstra 算法以找到最短距离
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

编译并运行上述代码，你将得到最短距离数组 [0, 27, 34, 18, 21, 25]。

总结

恭喜！你已经完成了实现 Dijkstra 算法的实验。你可以在 LabEx 中练习更多实验来提升你的技能。