Dijkstra's Algorithm Implementation
Given a weighted graph with non-negative edge weights, implement Dijkstra's algorithm to find the shortest path from a source node to all other nodes in the graph.
Constraints:
- The graph is represented as an adjacency list.
- The graph contains no negative weight edges.
- The source node is given as input.
Examples:
Input: [[0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0]]
Output: [0, 4, 12, 19, 21, 11, 9, 8, 14]
Explanation: The shortest distances from the source node (0) to all other nodes are calculated using Dijkstra's algorithm.
Solutions
Dijkstra's Algorithm
Dijkstra's algorithm works by maintaining a priority queue of nodes to visit, where the priority of each node is its current shortest distance from the source node. The algorithm repeatedly extracts the node with the minimum priority from the queue and updates the distances of its neighbors if a shorter path is found.
import java.util.PriorityQueue;
public
class Dijkstra {
public static int[] dijkstra(int[][] graph, int source) {
int[] distances = new int[graph.length];
for (int i = 0;
i < distances.length;
i++) distances[i] = Integer.MAX_VALUE;
distances[source] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[] {
source, 0 }
);
while (!pq.isEmpty()) {
int[] node = pq.poll();
if (node[1] > distances[node[0]]) continue;
for (int neighbor = 0;
neighbor < graph.length;
neighbor++) {
int weight = graph[node[0]][neighbor];
if (weight > 0 && distances[node[0]] + weight < distances[neighbor]) {
distances[neighbor] = distances[node[0]] + weight;
pq.offer(new int[] {
neighbor, distances[neighbor] }
);
}
}
}
return distances;
}
}Follow-up:
Implement A* algorithm to find the shortest path in a weighted graph with heuristic function.
