编辑代码

import java.util.*;

public class SingleSourceShortestPath {

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class Graph {
        List<List<Edge>> adjList;

        Graph(int numVertices) {
            adjList = new ArrayList<>(numVertices);
            for (int i = 0; i < numVertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjList.get(from).add(new Edge(to, weight));
        }
    }

    public static void dijkstra(Graph graph, int source) {
        int numVertices = graph.adjList.size();
        int[] distances = new int[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        PriorityQueue<Pair> minHeap = new PriorityQueue<>(Comparator.comparingInt(p -> p.distance));
        minHeap.offer(new Pair(source, 0));

        while (!minHeap.isEmpty()) {
            Pair current = minHeap.poll();
            int u = current.vertex;

            for (Edge neighbor : graph.adjList.get(u)) {
                int v = neighbor.to;
                int weight = neighbor.weight;

                if (distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    minHeap.offer(new Pair(v, distances[v]));
                }
            }
        }

        // 打印结果
        System.out.println("From source vertex " + source + ":");
        for (int i = 0; i < numVertices; i++) {
            System.out.println("To vertex " + i + ": " + (distances[i] == Integer.MAX_VALUE ? "Infinity" : distances[i]));
        }
    }

    static class Pair {
        int vertex;
        int distance;

        Pair(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        // 创建一个图
        Graph graph = new Graph(5);
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 5);
        graph.addEdge(1, 2, 2);
        graph.addEdge(1, 3, 1);
        graph.addEdge(2, 3, 9);
        graph.addEdge(2, 4, 4);
        graph.addEdge(3, 4, 3);

        // 运行 Dijkstra 算法
        dijkstra(graph, 0);
    }
}