Bellman-Ford with Adjacency List (Shortest-path with negative weights)

Question

I'm implementing my own version of the Bellman-Ford algorithm to find shortest paths with negative weights. However I'm not sure if this is correct, since in my opinion the complexity in my solution differs from the widely accepted Bellman-Ford complexity of O(|V||E| + |E|) = O(|V||E|).

For this I'm using an array A of adjacency lists for each vertex k in the graph. Each element in the adjacency list for vertex k, elem has two data members elem->vertex, corresponding to the edge (k , elem->vertex) and the weight elem->weight of the same edge. iS is the starting node and iT the end node.

I simplified the algorithm to just return the shortest distance from iS to iT


Bellman_Ford(A,iS,iT):
d <- new Array(A.size(),∞) // Distance array to vertex iS
d[iS] <- 0
for i <- 1 to A.size() - 1:
    for k <- 0 to A.size() - 1:
        for elem in A[k]:
            if d[k] + elem->weight < d[elem->vertex]:
                d[elem->vertex] <- d[k] + elem->weight

for k <- 0 to A.size() - 1:
    for elem in A[k]:
        if d[k] + elem->weight < d[elem->vertex]:
            throw "Negative cycle found"

return d[iT] // if iT not reachable by iS will return ∞

Because of the Adjacency list it seems to me that the complexity is then: O(|V|(|V|+|E|) for the first group of nested loops and O(|E|) for the negative cycle search, for a total complexity of:

O(|V|(|V|+|E|) + |E|) = O(|V|² + |V||E| + |E|) = O(|V|² + |V||E|)

Note that |E| can be O(|V|^2) (in a nearly complete graph) so that |V||E| would dominate |V|^2. — Unmitigated
– Unmitigated, Commented Jun 3, 2024 at 21:14
@user24714692 The implementation is already there: Whether if its in Pseudocode, or any other language will not change the asymptotic behaviour (algorithmic complexity), and thus I want to keep it language agnostic. — Michel H
– Michel H, Commented Jun 4, 2024 at 6:21
@Unmitigated: I understand where you're coming from, but a simplification is only possible the other way around: |V|^2 will always dominate |E|, since for the biggest |E|, |V|^2 will be at least equally big. In other words, for my term, unless we're explicitly dealing with a complete graph (which doesn't have to be the case), we cannot simplify further than O(|V|^2 + |V||E|) — Michel H
– Michel H, Commented Jun 4, 2024 at 6:25
I was referring to worst-case time complexity, which is what is often considered when discussing big O. But yes, the standard Bellman-Ford algorithm relies on having a list of edges beforehand; using an adjacency list will not be the same. — Unmitigated
– Unmitigated, Commented Jun 4, 2024 at 6:39

trincot · Accepted Answer · 2024-06-04 11:06:44Z

1

Your analysis is correct, but it only leads to a worse complexity -- compared to the standard complexity of Ө(|V||E|) -- when the graph has significantly fewer edges than vertices (and by consequence is not connected). In that case your implementation has a time complexity of Ө(|V|²) which is worse than the standard Ө(|V||E|). But when this is not so, i.e. when |E| is Ω(|V|), then Ө(|V|² + |V||E|) is Ө(|V||E|).

If you care about the graphs with relatively few edges, then you can adapt your implementation to avoid visiting vertices that have no outgoing edges. For instance, you could collect the k for which A[k] is not empty into a vector, and then use that vector in the main algorithm:

Bellman_Ford(A, iS, iT):
    // Collect vertices that have outgoing edge(s)
    connected ← new Vector()
    for k ← 0 to A.size() - 1:
        if A[k].size() > 0:
            connected.add(k);
            
    d ← new Array(A.size(), ∞) // Distance array to vertex iS
    d[iS] ← 0
    for i ← 1 to A.size() - 1:
        // Now this loop is guaranteed to make at most |E| iterations:
        for j ← 0 to connected.size() - 1:
            k = connected[j]
            for elem in A[k]: // Now guaranteed to make at least one iteration
                if d[k] + elem->weight < d[elem->vertex]:
                    d[elem->vertex] ← d[k] + elem->weight

    // And you might as well use the same approach here:
    for j ← 0 to connected.size() - 1:
        k = connected[j]
        for elem in A[k]:
            if d[k] + elem->weight < d[elem->vertex]:
                throw "Negative cycle found"
    
    return d[iT] // if iT not reachable by iS will return ∞

answered Jun 4, 2024 at 11:06

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Michel H Over a year ago

Thanks a lot! Unrelated question, how did you manage to get your algorithm colored? When it comes to syntax it seems equivalent to mine.

trincot Over a year ago

I tagged the code block with a language. So three backtics followed by cpp or java or any language

Collectives™ on Stack Overflow

Bellman-Ford with Adjacency List (Shortest-path with negative weights)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related