用Java编写dijkstra算法

非常感谢您的问题。我可以回答这个问题。Dijkstra算法是一种单源最短路径算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。该算法主要用于路由算法或作为其他图形算法的一个子模块。在这个算法中，我们从给定的源点开始，通过贪心的方法计算每个节点到源点的最短距离，最终得到所有数据点到源点的最短路径。Java编程语言可以用来实现Dijkstra算法。

相关问题

编写一个java的Dijkstra算法

以下是Java实现Dijkstra算法的代码，该算法用于在加权图中找到最短路径：

import java.util.*;

public class DijkstraAlgorithm {
    private static final Graph.Edge[] GRAPH = {
            new Graph.Edge("A", "B", 7),
            new Graph.Edge("A", "D", 5),
            new Graph.Edge("B", "C", 8),
            new Graph.Edge("B", "D", 9),
            new Graph.Edge("B", "E", 7),
            new Graph.Edge("C", "E", 5),
            new Graph.Edge("D", "E", 15),
            new Graph.Edge("D", "F", 6),
            new Graph.Edge("E", "F", 8),
            new Graph.Edge("E", "G", 9),
            new Graph.Edge("F", "G", 11)
    };

    private static final String START = "A";
    private static final String END = "G";

    public static void main(String[] args) {
        Graph graph = new Graph(GRAPH);
        graph.dijkstra(START);
        System.out.println(graph.getPath(END));
    }

    static class Graph {
        private final Map<String, Vertex> graph;

        static class Edge {
            final String v1, v2;
            final int dist;

            Edge(String v1, String v2, int dist) {
                this.v1 = v1;
                this.v2 = v2;
                this.dist = dist;
            }
        }

        static class Vertex implements Comparable<Vertex> {
            final String name;
            int dist = Integer.MAX_VALUE;
            Vertex previous = null;
            final Map<Vertex, Integer> neighbours = new HashMap<>();

            Vertex(String name) {
                this.name = name;
            }

            private void printPath() {
                if (this == this.previous) {
                    System.out.printf("%s", this.name);
                } else if (this.previous == null) {
                    System.out.printf("%s(unreached)", this.name);
                } else {
                    this.previous.printPath();
                    System.out.printf(" -> %s(%d)", this.name, this.dist);
                }
            }

            public int compareTo(Vertex other) {
                return Integer.compare(dist, other.dist);
            }
        }

        Graph(Edge[] edges) {
            graph = new HashMap<>(edges.length);

            for (Edge e : edges) {
                if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
                if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
            }

            for (Edge e : edges) {
                graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
            }
        }

        void dijkstra(String startName) {
            if (!graph.containsKey(startName)) {
                System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
                return;
            }
            final Vertex source = graph.get(startName);
            NavigableSet<Vertex> q = new TreeSet<>();

            for (Vertex v : graph.values()) {
                v.previous = v == source ? source : null;
                v.dist = v == source ? 0 : Integer.MAX_VALUE;
                q.add(v);
            }

            dijkstra(q);
        }

        private void dijkstra(final NavigableSet<Vertex> q) {
            Vertex u, v;
            while (!q.isEmpty()) {
                u = q.pollFirst();
                if (u.dist == Integer.MAX_VALUE) break;

                for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
                    v = a.getKey();

                    final int alternateDist = u.dist + a.getValue();
                    if (alternateDist < v.dist) {
                        q.remove(v);
                        v.dist = alternateDist;
                        v.previous = u;
                        q.add(v);
                    }
                }
            }
        }

        public List<String> getPath(String endName) {
            if (!graph.containsKey(endName)) {
                System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
                return Collections.emptyList();
            }

            return graph.get(endName).printPath();
        }
    }
}

编写以下程序：用java和Dijkstra 算法编写迷宫最短路径查找

好的，以下是Java实现Dijkstra算法查找迷宫最短路径的代码，建议在IDE中运行：

import java.util.*;

public class DijkstraMazeSolver {
    private static final int INF = Integer.MAX_VALUE; // 无穷大
    private static final int[] DIRS = {-1, 0, 1, 0, -1}; // 方向数组

    public static void main(String[] args) {
        // 迷宫地图
        int[][] maze = {
                {0, 0, 1, 0, 0, 0},
                {0, 0, 1, 0, 0, 0},
                {0, 0, 0, 0, 1, 0},
                {0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 1},
                {0, 0, 1, 0, 0, 0}
        };

        // 起点和终点
        int startX = 0, startY = 0;
        int endX = 5, endY = 5;

        // 使用Dijkstra算法求解最短路径
        int[][] dist = dijkstra(maze, startX, startY);

        // 输出最短距离和路径
        System.out.println("最短距离：" + dist[endX][endY]);
        System.out.println("最短路径：" + getPath(dist, endX, endY));
    }

    // Dijkstra算法求解最短路径
    private static int[][] dijkstra(int[][] maze, int startX, int startY) {
        int m = maze.length, n = maze[0].length;
        int[][] dist = new int[m][n]; // 起点到每个点的最短距离
        boolean[][] visited = new boolean[m][n]; // 是否访问过
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2])); // 小根堆

        // 初始化
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], INF);
        }
        dist[startX][startY] = 0;
        pq.offer(new int[]{startX, startY, 0});

        // Dijkstra算法
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], d = cur[2];
            if (visited[x][y]) {
                continue;
            }
            visited[x][y] = true;

            // 更新相邻节点的最短距离
            for (int k = 0; k < 4; k++) {
                int nx = x + DIRS[k], ny = y + DIRS[k + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0 && !visited[nx][ny]) {
                    int nd = d + 1;
                    if (nd < dist[nx][ny]) {
                        dist[nx][ny] = nd;
                        pq.offer(new int[]{nx, ny, nd});
                    }
                }
            }
        }

        return dist;
    }

    // 获取最短路径
    private static String getPath(int[][] dist, int endX, int endY) {
        int m = dist.length, n = dist[0].length;
        StringBuilder sb = new StringBuilder();
        int x = endX, y = endY;

        while (dist[x][y] != INF) {
            sb.insert(0, String.format("(%d, %d) ", x, y));
            for (int k = 0; k < 4; k++) {
                int nx = x + DIRS[k], ny = y + DIRS[k + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == dist[x][y] - 1) {
                    x = nx;
                    y = ny;
                    break;
                }
            }
        }

        return sb.toString();
    }
}

以上代码使用了Dijkstra算法（基于贪心策略）来求解迷宫最短路径，利用PriorityQueue实现了小根堆优化，时间复杂度为O(mnlog(mn))。可以根据实际情况进行修改。