forked from IamBisrutPyne/Java-Programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.java
More file actions
104 lines (85 loc) · 2.98 KB
/
Dijkstra.java
File metadata and controls
104 lines (85 loc) · 2.98 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.*;
class Dijkstra {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class Node {
int vertex, dist;
Node(int vertex, int dist) {
this.vertex = vertex;
this.dist = dist;
}
}
static void dijkstra(List<List<Edge>> adj, int source) {
int n = adj.size();
int[] dist = new int[n];
int[] parent = new int[n]; // for path reconstruction
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
dist[source] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.dist));
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node curr = pq.poll();
int u = curr.vertex;
if (curr.dist > dist[u]) continue;
for (Edge edge : adj.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
parent[v] = u; // keep track of the path
pq.offer(new Node(v, dist[v]));
}
}
}
// Print shortest distances and paths
System.out.println("\nShortest distances from node " + source + ":");
for (int i = 0; i < n; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.println("To " + i + " = INF (unreachable)");
} else {
System.out.print("To " + i + " = " + dist[i] + " | Path: ");
printPath(i, parent);
System.out.println();
}
}
}
static void printPath(int node, int[] parent) {
if (node == -1) return;
Stack<Integer> path = new Stack<>();
while (node != -1) {
path.push(node);
node = parent[node];
}
while (!path.isEmpty()) {
System.out.print(path.pop());
if (!path.isEmpty()) System.out.print(" -> ");
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of nodes: ");
int n = sc.nextInt();
System.out.print("Enter number of edges: ");
int edges = sc.nextInt();
List<List<Edge>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
System.out.println("Enter edges (u v weight):");
for (int i = 0; i < edges; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
adj.get(u).add(new Edge(v, w));
// For undirected graph, uncomment next line:
// adj.get(v).add(new Edge(u, w));
}
System.out.print("Enter starting node: ");
int source = sc.nextInt();
dijkstra(adj, source);
}
}