p425.2 Widest Path Problem

p425.2 Widest Path Problem.py

import heapq

def widest(graph, start = 0, INFINITY = 10**10):
    width = {}
    cloud = {}
    path = {}
    for x in graph:
        width[x] = INFINITY
        cloud[x] = False
        path[x] = (2,) #Optional, returns the actual path, useful for debugging
        
    width[start] = 0
    queue = [(2, 2)]
    while len(queue) != 0:
        
        wu, u = heapq.heappop(queue)
        
        cloud[u] = True
        
        if wu == INFINITY:
            break
        
        for v, w in graph[u]:
            if cloud[v] == False:
                alt = min(width[v], max(wu, w))
                if alt < width[v]:
                    path[v] = path[u] + (v,) #Optional, returns the actual path, useful for debugging
                    width[v] = alt
                    heapq.heappush(queue, (width[v], v))
                    
    return width, path