java实现dijkstra最短路径寻路算法

下面是Java实现Dijkstra最短路径寻路算法的完整攻略：

什么是Dijkstra最短路径寻路算法

Dijkstra算法是一种可以求解带权重图（有向或无向）中的最短路径的算法。该算法要求图的权重为非负值。

Dijkstra算法实现思路

• 首先我们需要初始化：所有点的到起点的距离为无穷大，但起点到自己的距离为0。
• 然后从起点开始，将起点标记为已访问过，并将其到与其相邻的点的距离记录下来。
• 在所有相邻的点中选取距离最小的点，标记为已访问，并更新其与其相邻的点的距离。
• 依次将与起点相邻的点标记为已访问，并更新它们与起点的距离，直到找到终点。

可以使用优先队列来实现上述思路，因为它可以按照距离大小进行排序。

Java程序示例

以下是一份简单的Java程序实现Dijkstra算法，该示例基于邻接矩阵来存储图：

import java.util.*;

public class DijkstraShortestPath {
    /** 邻接矩阵实现图 */
    private int graph[][];

    public DijkstraShortestPath(int[][] graph) {
        this.graph = graph;
    }

    /** Dijkstra实现方法 */
    public int[] dijkstra(int start) {
        // 将所有点的距离都初始化为无穷大
        int[] dist = new int[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 将起点到自己的距离定为0
        dist[start] = 0;

        // 使用优先队列实现
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Node(start, 0));

        while (!priorityQueue.isEmpty()) {
            Node node = priorityQueue.poll();
            int current = node.getValue();
            // 如果该点已经被访问过，无需再次访问
            if (node.getCost() != dist[current]) {
                continue;
            }

            // 更新neighbor的距离
            for (int next = 0; next < graph.length; next++) {
                int cost = graph[current][next];
                if (cost == Integer.MAX_VALUE) {
                    continue;
                }
                int distance = dist[current] + cost;
                if (dist[next] > distance) {
                    dist[next] = distance;
                    priorityQueue.offer(new Node(next, distance));
                }
            }
        }
        return dist;
    }

    /** 优先队列中存储的信息 */
    public class Node implements Comparable<Node>{
        int value;
        int cost;
        public Node(int value, int cost) {
            this.value = value;
            this.cost = cost;
        }

        public int getValue() {
            return value;
        }

        public int getCost() {
            return cost;
        }

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

    public static void main(String[] args) {
        int[][] graph = {
                { 0, 2, 3, 4, Integer.MAX_VALUE },
                { 2, 0, Integer.MAX_VALUE, Integer.MAX_VALUE, 6 },
                { 3, Integer.MAX_VALUE, 0, 3, 1 },
                { 4, Integer.MAX_VALUE, 3, 0, 5 },
                { Integer.MAX_VALUE, 6, 1, 5, 0 }
        };
        DijkstraShortestPath dijkstra = new DijkstraShortestPath(graph);
        int[] dist = dijkstra.dijkstra(0);
        System.out.println(Arrays.toString(dist));  // [0, 2, 3, 4, 5]
    }
}

在上述代码中，我们定义了一个邻接矩阵类型的图并实现了Dijkstra算法以计算从起点0到其余所有节点的最短距离（上述的邻接矩阵数组就是该图的数据结构）。