dijkstra

Dijkstra.py

from heapq import heappush, heappop
def dijkstra(adjList,s):
    num = len(adjList)
    dist = [10**8 for i in range(num)]
    prev = [-1 for i in range(num)]
    queue = []

    heappush(queue,(0,s))
    dist[s] = 0
    while len(queue) != 0:
        v_cost, v = heappop(queue)
        if dist[v] < v_cost:
            continue
        for u_cost, u in adjList[v]:
            if u != v and u_cost + dist[v] < dist[u]:
                prev[u] = v
                dist[u] = u_cost + dist[v]
                heappush(queue, (dist[u], u))
    return dist,prev