This gist test if SPFA can be performed with a stack. The result is, NO.

spfa.py

from collections import deque
import random
def gen_graph(n, m):
    a = [[None] * n for i in range(n)]
    for i in range(m):
        x = random.randint(0, n-1)
        y = random.randint(0, n-1)
        c = random.randint(1, 100)
        a[x][y] = c
    return a
def spfa_stk(n, s, a):
    """
    @n: number of nodes
    @s: start id
    @a: adjacent matrix
    @return: shortest path distance array
    """
    dist = [None] * n
    dist[s] = 0
    q = [s]
    inq = {s}
    while q:
        i = q.pop()
        for j in range(n):
            if a[i][j] is None: continue
            d = dist[i] + a[i][j]
            if dist[j] is None or d < dist[j]: 
                dist[j] = d
                if j not in inq:
                    q.append(j)
                    inq.add(j)
    return dist

def spfa_que(n, s, a):
    """
    @n: number of nodes
    @s: start id
    @a: adjacent matrix
    @return: shortest path distance array
    """
    q = deque([s])
    dist = [None] * n
    dist[s] = 0
    inq = {s}
    while q:
        i = q.popleft()
        for j in range(n):
            if a[i][j] is None: continue
            d = dist[i] + a[i][j]
            if dist[j] is None or d < dist[j]: 
                dist[j] = d
                if j not in inq:
                    q.append(j)
                    inq.add(j)
    return dist

def gen_dot(n, a):
    labels = ['p'+str(i) for i in range(n)]
    edges = []
    for i in range(n):
        for j in range(n):
            if a[i][j] is not None:
                edges.append((i, j, a[i][j]))
    s = """digraph{{
    rankdir=LR
    {edges}
}}""".format(edges='\n    '.join("{0}->{1}[label={2}]".format(
            labels[i], labels[j], c) for (i, j, c) in edges))
    return s
if __name__ == '__main__':
    import subprocess
    nTestCase = 1
    nNodes = 8
    nEdges = 20
    dotFile = '/tmp/graph.dot'
    for t in range(nTestCase):
        g = gen_graph(nNodes, nEdges)
        dist1 = spfa_stk(nNodes, 0, g)
        dist2 = spfa_que(nNodes, 0, g)
        if dist1 != dist2:
            print(False)
            # print(dist1)
            # print(dist2)
            open(dotFile, 'w').write(gen_dot(nNodes, g))
            p = subprocess.Popen(['xdot', dotFile])
            p.wait()
        else:
            print(True)