如何在 Dijkstra 算法中找到最近的未访问节点

简介

本教程将指导你完成在 Java 中实现 Dijkstra 算法并找出最近未访问节点的过程。Dijkstra 算法是一种广泛用于在图中查找节点之间最短路径的技术，了解如何高效地选择下一个要访问的节点对于优化你的 Java 代码至关重要。

Skills Graph

理解 Dijkstra 算法

Dijkstra 算法是一种广为人知的图遍历算法，用于在带权图中找到两个节点之间的最短路径。它以荷兰计算机科学家 Edsger Dijkstra 的名字命名，他于 1959 年首次提出了该算法。

该算法的工作原理是迭代地选择距离起始节点已知距离最小的未访问节点，然后更新其所有相邻节点的距离。这个过程会一直持续，直到算法找到图中所有节点的最短路径。

Dijkstra 算法的关键步骤如下：

1. 初始化起始节点

• 将起始节点的距离设置为 0，其他所有节点的距离设置为无穷大。
• 将所有节点标记为未访问。

2. 选择最近的未访问节点

• 找到距离起始节点已知距离最小的未访问节点。
• 这个节点成为“当前”节点。

3. 更新相邻节点的距离

• 对于当前节点的每个邻居，通过将当前节点的距离与当前节点和邻居之间边的权重相加，计算从起始节点到该邻居的距离。
• 如果这个新距离小于邻居的当前距离，则更新邻居的距离。

4. 将当前节点标记为已访问

• 一旦一个节点的距离确定，将其标记为已访问，这样它就不会再被考虑。

5. 重复步骤 2 - 4，直到所有节点都被访问

• 继续选择最近的未访问节点并更新其邻居距离的过程，直到所有节点都被访问。

通过遵循这些步骤，Dijkstra 算法能够有效地找到起始节点与图中所有其他节点之间的最短路径。

找出最近的未访问节点

Dijkstra 算法的关键步骤之一是在每次迭代中找出最近的未访问节点。这对于确保算法选择能得出最短总路径的节点至关重要。

维护一个优先队列

为了有效地跟踪未访问节点及其到起始节点的距离，Dijkstra 算法通常使用优先队列数据结构。优先队列存储未访问节点，距离起始节点最近的节点位于队列前端。

以下是一个示例，展示了你如何使用 Java 的 PriorityQueue 类来实现这一点：

import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    int id;
    int distance;

    Node(int id, int distance) {
        this.id = id;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class DijkstraExample {
    public static void findShortestPath(int[][] graph, int startNode) {
        int numNodes = graph.length;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] distances = new int[numNodes];

        // 初始化距离并将起始节点添加到优先队列
        for (int i = 0; i < numNodes; i++) {
            distances[i] = Integer.MAX_VALUE;
        }
        distances[startNode] = 0;
        pq.offer(new Node(startNode, 0));

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int currentId = currentNode.id;

            // 跳过已访问节点
            if (distances[currentId] < currentNode.distance) {
                continue;
            }

            // 更新相邻节点的距离
            for (int neighbor = 0; neighbor < numNodes; neighbor++) {
                if (graph[currentId][neighbor]!= 0) {
                    int newDistance = distances[currentId] + graph[currentId][neighbor];
                    if (newDistance < distances[neighbor]) {
                        distances[neighbor] = newDistance;
                        pq.offer(new Node(neighbor, newDistance));
                    }
                }
            }
        }

        // 打印最终距离
        for (int i = 0; i < numNodes; i++) {
            System.out.println("Distance from " + startNode + " to " + i + ": " + distances[i]);
        }
    }
}

在这个示例中，我们创建了一个自定义的 Node 类，它实现了 Comparable 接口，以便 PriorityQueue 能够根据节点到起始节点的距离对节点进行排序。然后，我们使用优先队列在算法的每次迭代中有效地选择最近的未访问节点。

通过使用优先队列，Dijkstra 算法能够以 O((V + E) log V) 的时间复杂度找到起始节点与图中所有其他节点之间的最短路径，其中 V 是节点数，E 是图中的边数。

在 Java 中实现 Dijkstra 算法

既然我们已经对 Dijkstra 算法以及如何找出最近的未访问节点有了深入理解，那就深入探讨一下在 Java 中的实现。

逐步实现

1. 初始化起始节点：将起始节点的距离设为 0，其他所有节点的距离设为无穷大。将所有节点标记为未访问。
2. 创建一个优先队列：使用 PriorityQueue 来存储未访问节点，距离起始节点最近的节点位于队列前端。
3. 选择最近的未访问节点：反复从优先队列中取出距离最小的节点。这个节点成为“当前”节点。
4. 更新相邻节点的距离：对于当前节点的每个邻居，通过将当前节点的距离与当前节点和邻居之间边的权重相加，计算从起始节点到该邻居的距离。如果这个新距离小于邻居的当前距离，则更新邻居的距离并将其添加到优先队列中。
5. 将当前节点标记为已访问：一旦一个节点的距离确定，将其标记为已访问，这样它就不会再被考虑。
6. 重复步骤 3 - 5，直到所有节点都被访问：继续选择最近的未访问节点并更新其邻居距离的过程，直到所有节点都被访问。

示例代码

以下是 Dijkstra 算法在 Java 中的示例实现：

import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    int id;
    int distance;

    Node(int id, int distance) {
        this.id = id;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class DijkstraExample {
    public static void findShortestPath(int[][] graph, int startNode) {
        int numNodes = graph.length;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] distances = new int[numNodes];
        boolean[] visited = new boolean[numNodes];

        // 初始化距离并将起始节点添加到优先队列
        for (int i = 0; i < numNodes; i++) {
            distances[i] = Integer.MAX_VALUE;
        }
        distances[startNode] = 0;
        pq.offer(new Node(startNode, 0));

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int currentId = currentNode.id;

            // 跳过已访问节点
            if (visited[currentId]) {
                continue;
            }
            visited[currentId] = true;

            // 更新相邻节点的距离
            for (int neighbor = 0; neighbor < numNodes; neighbor++) {
                if (graph[currentId][neighbor]!= 0) {
                    int newDistance = distances[currentId] + graph[currentId][neighbor];
                    if (newDistance < distances[neighbor]) {
                        distances[neighbor] = newDistance;
                        pq.offer(new Node(neighbor, newDistance));
                    }
                }
            }
        }

        // 打印最终距离
        for (int i = 0; i < numNodes; i++) {
            System.out.println("Distance from " + startNode + " to " + i + ": " + distances[i]);
        }
    }
}

此实现遵循前面概述的步骤，在每次迭代中使用 PriorityQueue 有效地选择最近的未访问节点。Node 类用于存储节点 ID 及其到起始节点的距离，并且实现了 compareTo 方法，以便优先队列能够根据距离对节点进行排序。

通过在合适的图表示上运行此代码，你可以找到从起始节点到图中所有其他节点的最短路径。

总结

在本 Java 教程结束时，你将全面理解 Dijkstra 算法以及找出最近未访问节点的策略。这些知识将使你能够编写高效且有效的 Java 代码来解决图遍历和最短路径问题。