<jupyter_start><jupyter_text>Run time: $O(E + V\log(V))$.<jupyter_code>import heapq
import math

def dijkstra(G, src):
    # G is an adjacency list of: v_i -> [v_j, v_k, ...]
    Q = []
    cost = {node: float('inf') for node in G.keys()}
    cost[src] = 0
    parent = {src: None}
    visited = set()
    heapq.heappush(Q, (cost[src], src))
    
    while len(Q) > 0:
        c, node = heapq.heappop(Q)
        for neighbor, distance in G[node]:
            if neighbor not in visited:
                if cost[node] + distance < cost[neighbor]:
                    cost[neighbor] = cost[node] + distance
                    parent[neighbor] = node
                    heapq.heappush(Q, (cost[neighbor], neighbor))
                    
    return cost, parent

def reconstruct_path(parent, src, target):
    node = target
    path = []
    
    while node != None:
        path.insert(0, node)
        node = parent[node]

    return path

def shortest_path(G, src, target):
    cost, parent = dijkstra(G, 0)
    return reconstruct_path(parent, 0, 3)        
                    
def main():
    G = {0: [(1, 2), (2, 1)], 1: [(3, 2)], 2: [(3, 1)], 3: []}
    path = shortest_path(G, 0, 3) 
    print path
    
if __name__ == "__main__":
    main()<jupyter_output>[0, 2, 3]
{'fraction_non_alphanumeric': 0.14858490566037735, 'fraction_numerical': 0.018081761006289308, 'mean_word_length': 1.981264637002342, 'pattern_counts': {'":': 1, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '228567', 'license': 'MIT', 'n_tokens_mistral': 477, 'n_tokens_neox': 442, 'n_words': 123, 'path': 'Dijkstra.ipynb', 'repo_name': 'abeschneider/algorithm_notes', 'size': '1272'}