Programs & Examples
Data Structures in Java · Study material
Shortest road distance with Dijkstra's algorithm
Dijkstra combines two data structures from this page: an adjacency list for the road network and a PriorityQueue that always hands back the closest unsettled city. Each city also remembers its predecessor so the route can be rebuilt.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Main {
record Edge(String to, int km) { }
public static void main(String[] args) {
// Weighted, undirected road network as an adjacency list
Map<String, List<Edge>> g = new LinkedHashMap<>();
String[][] roads = {{"Pune", "Mumbai", "150"}, {"Pune", "Nashik", "210"}, {"Mumbai", "Nashik", "165"},
{"Mumbai", "Surat", "280"}, {"Nashik", "Surat", "250"}, {"Pune", "Satara", "110"},
{"Satara", "Kolhapur", "120"}};
for (String[] r : roads) {
int km = Integer.parseInt(r[2]);
g.computeIfAbsent(r[0], k -> new ArrayList<>()).add(new Edge(r[1], km));
g.computeIfAbsent(r[1], k -> new ArrayList<>()).add(new Edge(r[0], km));
}
Map<String, Integer> dist = new TreeMap<>();
Map<String, String> prev = new HashMap<>();
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(Map.Entry.<String, Integer>comparingByValue());
dist.put("Pune", 0);
pq.add(Map.entry("Pune", 0));
while (!pq.isEmpty()) {
Map.Entry<String, Integer> cur = pq.poll(); // closest unsettled city
String u = cur.getKey();
int d = cur.getValue();
if (d > dist.get(u)) continue; // stale queue entry – skip it
for (Edge e : g.get(u)) {
int nd = d + e.km();
if (nd < dist.getOrDefault(e.to(), Integer.MAX_VALUE)) { // found a shorter route
dist.put(e.to(), nd);
prev.put(e.to(), u);
pq.add(Map.entry(e.to(), nd));
}
}
}
System.out.println(dist);
Deque<String> path = new ArrayDeque<>();
for (String at = "Surat"; at != null; at = prev.get(at)) path.addFirst(at); // walk back from the target
System.out.println(String.join(" -> ", path) + " = " + dist.get("Surat") + " km");
}
}
{Kolhapur=230, Mumbai=150, Nashik=210, Pune=0, Satara=110, Surat=430}
Pune -> Mumbai -> Surat = 430 kmBracket matching with a stack
The stack example pushes every opening bracket and pops on each closing one; a mismatch, a pop from an empty stack, or leftovers at the end mean the expression is unbalanced.
Distances and components with BFS and DFS
The graph example uses BFS to compute each vertex's distance in edges from A, and repeated DFS to count connected components.