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方法来计算从起点到终点的最短路径。最后，我们打印出了这条路径。