1import java.util.*;
2
3class Graph {
4    private int v;
5    private List<List<Pair<Integer, Integer>>>> adj;
6
7    public Graph(int vertices) {
8        v = vertices;
9        adj = new ArrayList<>();
10        for (int i = 0; i < v; i++)
11            adj.add(new ArrayList<>());
12    }
13
14    public void addEdge(int src, int dest, int weight) {
15        adj.get(src).add(new Pair<>(dest, weight));
16        adj.get(dest).add(new Pair<>(src, weight));
17    }
18
19    public void dijkstra(int src) {
20        int[] dist = new int[v];
21        Arrays.fill(dist, Integer.MAX_VALUE);
22
23        PriorityQueue<Pair<Integer, Integer>>>> pq = new PriorityQueue<>(v, new Comparator<>() {
24            public int compare(Pair<Integer, Integer>>>> p1, Pair<Integer, Integer>>>> p2) {
25                int key1 = p1.getValue();
26                int key2 = p2.getValue();
27                return key1 - key2;
28            }
29        });
30
31        dist[src] = 0;
32        pq.add(new Pair<>(src, 0));
33
34        while (!pq.isEmpty()) {
35            int u = pq.poll().getKey();
36
37            for (Pair<Integer, Integer>>>> neighbor : adj.get(u)) {
38                int v = neighbor.getKey();
39                int weight = neighbor.getValue();
40
41                if (dist[u] + weight < dist[v]) {
42                    dist[v] = dist[u] + weight;
43                    pq.add(new Pair<>(v, dist[v]));
44                }
45            }
46        }
47
48        // Print the shortest paths
49        System.out.println("Vertex\t\tDistance from Source");
50        for (int i = 0; i < v; ++i)
51            System.out.println(i + "\t\t" + dist[i]);
52    }
53}
54
55public class ShortestPaths {
56    public static void main(String[] args) {
57        int vertices = 5;
58        int src = 0;
59
60        Graph graph = new Graph(vertices);
61
62        graph.addEdge(0, 1, 4);
63        graph.addEdge(0, 2, 2);
64        graph.addEdge(1, 2, 1);
65        graph.addEdge(1, 3, 3);
66        graph.addEdge(2, 3, 4);
67        graph.addEdge(3, 4, 2);
68
69        graph.dijkstra(src);
70    }
71}