Dijkstra algorithm

• graph = {u : [(v, w(u,v)), ..], ... }

  def dijkstra(graph: List[List[Tuple[int, float]]], source: int) -> List[float]:
    n = len(graph)
    distances: List[float] = [math.inf] * n
    distances[source] = 0.0
    heap: List[Tuple[float, int]] = [(0.0, source)]
  
    while heap:
        curr_dist, node = heapq.heappop(heap)
        if curr_dist > distances[node]:
            continue
          
        for neighbour, weight in graph[node]:
            dist = curr_dist + weight
            if dist < distances[neighbour]:
                distances[neighbour] = dist
                heapq.heappush(heap, (dist, neighbour))
      
    return distances
  

• $T(n) = O( (V+E) \log V)$
  • $O(V \log{V})$: Extract the minimum node from the heap for each vertex.
  • $O(E \log{V})$: Time taken to insert or update distances for each edge.
• $S(n) = O(V)$