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 sys, heapq
def dijkstra(graph, source):
distances = [sys.maxsize] * len(graph)
distances[source] = 0
pq = [(0, source)]
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in enumerate(graph[node]):
if weight > 0 and distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
heapq.heappush(pq, (distances[neighbor], neighbor))
return distancesFollow-up:
Implement A* algorithm to find the shortest path in a weighted graph with heuristic function.
