java djikstra 27s algorithm

1import java.util.*; 
2public class DPQ { 
3    private int dist[]; 
4    private Set<Integer> settled; 
5    private PriorityQueue<Node> pq; 
6    private int V; // Number of vertices 
7    List<List<Node> > adj; 
8  
9    public DPQ(int V) 
10    { 
11        this.V = V; 
12        dist = new int[V]; 
13        settled = new HashSet<Integer>(); 
14        pq = new PriorityQueue<Node>(V, new Node()); 
15    } 
16  
17    // Function for Dijkstra's Algorithm 
18    public void dijkstra(List<List<Node> > adj, int src) 
19    { 
20        this.adj = adj; 
21  
22        for (int i = 0; i < V; i++) 
23            dist[i] = Integer.MAX_VALUE; 
24  
25        // Add source node to the priority queue 
26        pq.add(new Node(src, 0)); 
27  
28        // Distance to the source is 0 
29        dist[src] = 0; 
30        while (settled.size() != V) { 
31  
32            // remove the minimum distance node  
33            // from the priority queue  
34            int u = pq.remove().node; 
35  
36            // adding the node whose distance is 
37            // finalized 
38            settled.add(u); 
39  
40            e_Neighbours(u); 
41        } 
42    } 
43  
44    // Function to process all the neighbours  
45    // of the passed node 
46    private void e_Neighbours(int u) 
47    { 
48        int edgeDistance = -1; 
49        int newDistance = -1; 
50  
51        // All the neighbors of v 
52        for (int i = 0; i < adj.get(u).size(); i++) { 
53            Node v = adj.get(u).get(i); 
54  
55            // If current node hasn't already been processed 
56            if (!settled.contains(v.node)) { 
57                edgeDistance = v.cost; 
58                newDistance = dist[u] + edgeDistance; 
59  
60                // If new distance is cheaper in cost 
61                if (newDistance < dist[v.node]) 
62                    dist[v.node] = newDistance; 
63  
64                // Add the current node to the queue 
65                pq.add(new Node(v.node, dist[v.node])); 
66            } 
67        } 
68    } 
69  
70    // Driver code 
71    public static void main(String arg[]) 
72    { 
73        int V = 5; 
74        int source = 0; 
75  
76        // Adjacency list representation of the  
77        // connected edges 
78        List<List<Node> > adj = new ArrayList<List<Node> >(); 
79  
80        // Initialize list for every node 
81        for (int i = 0; i < V; i++) { 
82            List<Node> item = new ArrayList<Node>(); 
83            adj.add(item); 
84        } 
85  
86        // Inputs for the DPQ graph 
87        adj.get(0).add(new Node(1, 9)); 
88        adj.get(0).add(new Node(2, 6)); 
89        adj.get(0).add(new Node(3, 5)); 
90        adj.get(0).add(new Node(4, 3)); 
91  
92        adj.get(2).add(new Node(1, 2)); 
93        adj.get(2).add(new Node(3, 4)); 
94  
95        // Calculate the single source shortest path 
96        DPQ dpq = new DPQ(V); 
97        dpq.dijkstra(adj, source); 
98  
99        // Print the shortest path to all the nodes 
100        // from the source node 
101        System.out.println("The shorted path from node :"); 
102        for (int i = 0; i < dpq.dist.length; i++) 
103            System.out.println(source + " to " + i + " is "
104                               + dpq.dist[i]); 
105    } 
106} 
107  
108// Class to represent a node in the graph 
109class Node implements Comparator<Node> { 
110    public int node; 
111    public int cost; 
112  
113    public Node() 
114    { 
115    } 
116  
117    public Node(int node, int cost) 
118    { 
119        this.node = node; 
120        this.cost = cost; 
121    } 
122  
123    @Override
124    public int compare(Node node1, Node node2) 
125    { 
126        if (node1.cost < node2.cost) 
127            return -1; 
128        if (node1.cost > node2.cost) 
129            return 1; 
130        return 0; 
131    } 
132} 
133