Shortest Path Algorithms

function dijkstra(graph, source):
    // Initialize distances and visited set
    distances = {}
    visited = set()
    pq = MinHeap()  // Priority queue
    
    // Set all distances to infinity, source to 0
    for each vertex v in graph:
        distances[v] = INFINITY
    distances[source] = 0
    pq.insert(source, 0)
    
    while pq is not empty:
        current = pq.extractMin()
        
        if current in visited:
            continue
            
        visited.add(current)
        
        // Relax all neighbors
        for each neighbor of current:
            weight = graph.getWeight(current, neighbor)
            newDistance = distances[current] + weight
            
            if newDistance < distances[neighbor]:
                distances[neighbor] = newDistance
                pq.insert(neighbor, newDistance)
    
    return distances