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

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|)

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 ∞