SPFA Shortest Path Algorithm (Python)

in #programming2 months ago

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

Coin Marketplace

STEEM 0.22
TRX 0.06
JST 0.025
BTC 18807.15
ETH 1295.03
USDT 1.00
SBD 2.51