SPFA Implementation

Here is the solution:

dist := [inf] * n
dist[src] := 0
queue := deque([src])
in_queue := [false] * n
in_queue[src] := true

while queue not empty
    u := queue.pop_front()
    in_queue[u] := false
    for (v, w) in adj[u]
        if dist[u] + w < dist[v] then
            dist[v] := dist[u] + w
            if not in_queue[v] then
                queue.push_back(v)
                in_queue[v] := true

Tracking $in\_queue$ prevents duplicate insertions. You only add a node if it is not already in the queue, avoiding redundant work.

This runs in $O(VE)$ time and uses $O(V)$ space.