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算法实现单源最短路径。该算法的思路是从源点开始，每次选择当前距离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其他所有点的最短路径。具体实现可以参考引用中的代码实现部分和引用中的算法思路和正确性分析部分。