SWE2009
Lab Assignment – 05
Name: Chakkilam Tarun Siddardha
Reg No: 21MIC7027
1) Implement Dijkstra’s Algorithm
Code:
import java.util.*;
class Graph {
private int vertices;
private List<List<NodeA>> adj;
public Graph(int vertices) {
this.vertices = vertices;
adj = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v, int weight) {
adj.get(u).add(new NodeA(v, weight));
adj.get(v).add(new NodeA(u, weight));
}
public void dijkstra(int src) {
PriorityQueue<NodeA> pq = new PriorityQueue<>(vertices, new
NodeA());
int[] dist = new int[vertices];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
pq.add(new NodeA(src, 0));
while (!pq.isEmpty()) {
int u = pq.poll().node;
for (NodeA neighbor : adj.get(u)) {
int v = neighbor.node;
int weight = neighbor.cost;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new NodeA(v, dist[v]));
}
}
}
for (int i = 0; i < vertices; i++) {
System.out.println("Vertex: " + i + " Distance from Source: " +
dist[i]);
}
}
}
class NodeA implements Comparator<NodeA> {
public int node;
public int cost;
public NodeA() {}
public NodeA(int node, int cost) {
this.node = node;
this.cost = cost;
}
public int compare(NodeA n1, NodeA n2) {
return Integer.compare(n1.cost, n2.cost);
}
}
public class Dijkstra {
public static void main(String[] args) {
int vertices = 5;
Graph graph = new Graph(vertices);
graph.addEdge(0, 1, 9);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(0, 4, 3);
graph.addEdge(2, 1, 2);
graph.addEdge(2, 3, 4);
graph.dijkstra(0);
}
}
Output:
