import math


def dijkstra_predecessor_and_distance(graph, source, weight='cost'):
    """
    Shortest paths via Dijkstra's algorithm,
    consistent with pseudocode on Slide 5-14.
    """

    # Definitions consistent with Kurose & Ross
    u = source

    def c(x, y):
        return graph[x][y][weight]
    N = frozenset(graph.nodes())
    NPrime = {u}  # i.e. "set([u])"
    D = dict.fromkeys(N, math.inf)
    P = {}  # create predecessor dictionary, to return

    # Initialization
    for v in N:
        P[v] = []
        if graph.has_edge(u, v):
            D[v] = c(u, v)
            P[v] = [u]  # add coresponding predecessor

    D[u] = 0  # over-write inf entry for source

    # Loop
    while NPrime != N:
        candidates = {w: D[w] for w in N if w not in NPrime}
        w, Dw = min(candidates.items(), key=lambda item: item[1])
        NPrime.add(w)

        for v in graph[w]:
            if v not in NPrime:
                DvNew = D[w] + c(w, v)
                if DvNew < D[v]:
                    D[v] = DvNew
                    # add node and its predecessor to predecessor dictionary
                    P[v] = [w]
    return P, D