java单源最短路径dijkstra

Dijkstra算法是一种用于解决单源最短路径问题的算法，它可以在有向图或无向图中找到从源节点到所有其他节点的最短路径。该算法的基本思想是从源节点开始，依次遍历所有节点，并计算出从源节点到每个节点的最短路径。在遍历过程中，需要维护一个距离数组，用于记录每个节点到源节点的距离，并不断更新距离数组中的值。同时，还需要维护一个已访问节点集合，用于记录已经访问过的节点，避免重复访问。最终，当所有节点都被访问过后，距离数组中的值即为从源节点到每个节点的最短路径。

相关问题

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);
                    }
                }
            }
        }

        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();
        }
    }
}

该示例代码实现了一个简单的图，其中包含了一些边和顶点。在main方法中，我们创建了一个Graph对象，并调用了它的dijkstra方法来计算从起点到终点的最短路径。最后，我们打印出了这条路径。

用java设计单源最短路径

在Java中，我们可以使用Dijkstra算法或者Floyd-Warshall算法来设计一个解决单源最短路径问题的程序。这里我们以Dijkstra算法为例，它是最常用的求解这个问题的有效方法。

Dijkstra算法步骤大致如下：

1. **初始化**：创建一个距离数组，将所有节点的距离设置为无穷大（通常使用整数最大值），起点（源节点）的距离设为0。

2. **优先队列**：使用最小堆（PriorityQueue）存储待处理的节点，初始只包含起点，并将其插入堆中。

3. **迭代过程**：直到堆为空或找到终点：
- 弹出当前节点，更新其邻居节点的距离，如果通过这个节点到达邻居的距离比已知更短，则更新邻居节点的距离，并将其加入堆中。

4. **路径跟踪**：当终点被找到并且其距离已经被标记为非负，说明找到了最短路径。从终点开始回溯，记录下每一步的前驱节点，直到起点。

以下是简单的Java代码框架示例：

import java.util.*;

public class Dijkstra {
    private List<Node> graph;
    // ...其他辅助数据结构和方法...

    public List<Node> dijkstra(Node start) {
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        Node[] distances = new Node[graph.size()];
        Arrays.fill(distances, null);
        distances[start.index] = start; // 设置起始点距离为0

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current == endNode) break;

            for (Edge edge : current.edges) {
                int distance = current.distance + edge.weight;
                if (distances[edge.toIndex] == null || distance < distances[edge.toIndex].distance) {
                    distances[edge.toIndex] = new Node(edge.to, distance);
                    queue.offer(distances[edge.toIndex]);
                }
            }
        }

        return buildPath(start, distances[endNode.index]);
    }

    private List<Node> buildPath(Node start, Node end) {
        List<Node> path = new ArrayList<>();
        Node current = end;
        while (current != null) {
            path.add(current);
            current = current.prev;
        }
        Collections.reverse(path);
        return path;
    }
}

在这个例子中，`Node`代表图中的一个节点，包含索引、邻接边以及到目标节点的距离等信息；`Edge`表示连接两个节点的边，包含权重。