Shortest Path Algorithms
Finding the shortest path between nodes is a classic graph problem. For weighted graphs, Dijkstra's algorithm works for non-negative weights; Bellman-Ford handles negative edges.
Dijkstra's Algorithm (non-negative weights)
Uses a priority queue to greedily select the node with smallest distance. Time O((V+E) log V).
public int[] dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0];
int d = curr[1];
if (d > dist[u]) continue;
for (Edge e : adjList[u]) {
int v = e.to, w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
Bellman-Ford Algorithm (handles negative edges)
Relax edges V-1 times, then check for negative cycles. Time O(VE).
Two Minute Drill
- Dijkstra: O((V+E) log V), requires non-negative weights.
- Bellman-Ford: O(VE), handles negative edges, detects negative cycles.
- Both compute shortest path from source to all nodes.
- Used in GPS navigation, network routing.
Need more clarification?
Drop us an email at career@quipoinfotech.com