SPFA Shortest Path Algorithm (Python)

SPFA (Shorter Path Faster Algorithm) is an improvement of Bellford-man Shortest Path Algorithm.

        def spfa(s, e):
            if s == e:
                return 0
            q = deque([s])
            d = { s: 0 }
            while q:
                v = q.popleft()
                for x, w in G[v]:
                    if d[v] + w < d.get(x, inf):
                        d[x] = d[v] + w
                        if x not in q:
                            q.append(x)
            return d.get(e, -1)

SPFA uses a queue rather than priority queue, and push the new vertex only if it is not in the queue. It is similar to Dijkstra single-source shortest path algorithm.

Check for more shortest path algorithms at blog