Levit's algorithm (also "Pape-Levit's") for finding the shortest paths from one `start` node to all another, Python 3 implementation.

levit.py

'''
Levit's algorithm for finding the shortest path from one `start` node to all another.
Written according to this article: https://goo.gl/GoeKS5
Doesn't work with negative cycles.
See example at the end.
'''
from collections import defaultdict, OrderedDict
from itertools import chain
from math import inf

class IndexedQueue(OrderedDict):
    "Queue-like container with fast search"
    def push(self, item):
        self[item] = None

    def pop(self):
        return OrderedDict.popitem(self, last=False)[0]

"(d,(c,(b,(a,())))) => (a, b, c, d)"
restore_path = lambda tup: (*restore_path(tup[1]),tup[0]) if tup else ()
      
def levit(gr, start, end=None):
    '''
    `gr` is an adjancety list { u:[(v, cost), ...] | (u,v) ∈ E },
    `end` is the desired target node, yet all graph nodes are processed anyway.
    Returns cost and path if `end` is provided.
    Else returns costs and paths as dicts. `restore_path(paths[end])` should be used for each desired end node.
    '''
    dist = defaultdict(lambda: inf)
    dist[start] = 0
    path = {start:(start,())}
    m0 = set()
    m1, m1_urg = IndexedQueue.fromkeys([start]), IndexedQueue()
    m2 = set(chain.from_iterable((v for v, _ in from_u) for from_u in gr.values())) - {start} #(u,v)∈E => v∈m2
    
    def relax(u, v, w):
        if (dist[v] > dist[u] + w):
            dist[v] = dist[u] + w
            path[v] = (v, path[u])
            return True
        return False

    while m1 or m1_urg:
        u = m1_urg.pop() if m1_urg else m1.pop()
        for v, c in gr.get(u, ()):
            if v in m2:
                m1.push(v)
                m2.discard(v)
                relax(u, v, c)
            elif v in m1:
                relax(u, v, c)
            elif v in m0 and relax(u, v, c):
                m1_urg.push(v)
                m0.discard(v)
        m0.add(u)
    
    if end is None:
        return dist, path
    elif end in path:
        return dist[end], restore_path(path[end])
    else:
        return inf, ()
                
if __name__ == '__main__':
    edges = [('a', 'b', 1), ('b', 'c', 2), ('c', 'a', 0), ('c', 'd', 1), ('a', '5', 5)]
    adj_list = defaultdict(list)
    for u, v, w in edges:
        adj_list[u].append((v, w))
    print(adj_list)

    cost, path = levit(adj_list, 'a', 'd')
    print(cost, path) # => 4 ('a', 'b', 'c', 'd')

    costs, paths = levit(adj_list, 'a')
    targets = ['b', 'c', 'd']
    for t in targets:
        print(costs[t], restore_path(paths[t]))

you dont actually need function

restore_path = lambda tup: (*restore_path(tup[1]),tup[0]) if tup else ()

for unpacking path tuples
its simpler to just path[v] = (v, *path[u]) in relax function

(1, *(2, 3, 4)) == (1, 2, 3, 4)