Bellman Ford Algorithm not detecting negative weight cycles and won't work with alternate sources

Question

I've been trying to implement a bellman ford algorithm in python but I'm having two issues: it won't detect negative weight cycles, nor will it properly print for sources other than a source of 1.

My code is as follows:

def bellman_ford(graph, source):
    num_nodes = 0
    vertices = [[array[0], array[1]] for array in graph]
    uniquevalues = list(set(i for j in vertices for i in j))
    for item in uniquevalues:
        num_nodes = num_nodes + 1

    distance = {i : float("Inf") for i in uniquevalues}
    distance[source] = 0
 
    for _ in range(len(vertices) - 1):
        for source, dest, cost in graph:
            if distance[source] != float("Inf") and distance[source] + cost < distance[dest]:
                distance[dest] = distance[source] + cost


    # Check for negative weight cycles
    for source, dest, cost in graph:
        if distance[source] != float("Inf") and distance[source] + cost < distance[dest]:
            print("Graph contains a negative-weight cycle")
            return None
    return distance

graph = [
    (1, 2, -2),
    (1, 3, 1),
    (2, 3, -2),
]

shortest_path = bellman_ford(graph, 1)
print(shortest_path)

and it will print: {1: 0, 2: -2, 3: -4}

If I were to change the source node to 3 it would print: {1: inf, 2: inf, 3: 0}

I've checked solutions from chatGPT and it doesn't seem to know how to make an algorithm that detects negative edges either, so I'm wondering if it's just IntelliJ being weird or I'm just not understanding something crucial. All help is appreciated.

Oddly enough, if I swap < distance[dest]: for < distance[source]: in the check for negative cycles it will properly detect the negative cycle, though I don't think this is how the algorithm is supposed to work.

Answer 1

it won't detect negative weight cycles, nor will it properly print for sources other than a source of 1

This is a misunderstanding. Although there is a bug, you are drawing wrong conclusions because of the assumption that the input graph has a negative cycle.

I'm wondering if it's just IntelliJ being weird

You could just run the code in another environment and see that the behaviour is not related to IntelliJ.

if I swap < distance[dest]: for < distance[source]: in the check for negative cycles it will properly detect the negative cycle

Randomly changing code is hardly ever the way to fix an issue. However in this case it could have given you a hint that...

Your input graph does not have a negative cycle. It represents this graph:

We could inverse the edge between nodes 1 and 3, to get:

This would be encoded as:

graph = [
    (1, 2, -2),
    (3, 1, 1),
    (2, 3, -2),
]

With this input you'll get the desired results.

Still, there is a bug in your code, caused by misleading names. The first loop is supposed to iterate ||−1 times, but it actually iterates ||−1 times. Your vertices variable does not represent vertices, but edges.

Some other remarks on your code (not problems):

• You don't need to call set for creating the set. Use brace-syntax. Also, you don't need to convert that set back to a list.
• There is no need for a loop to get the number of nodes. len(uniquevalues) is what you need.
• There is no need to first check if a distance is different from infinity. The condition that follows is guaranteed to be False when it would be infinity.

Here is the updated code (and input):

def bellman_ford(graph, source):
    # Use better name: this is a collection of edges, not of vertices
    edges = [array[:2] for array in graph]
    # Use descriptive names instead of `i` or `j`, and brace syntax
    uniquevalues = {vertex for edge in edges for vertex in edge}
    # No need for a loop to determine the number of nodes:
    num_nodes = len(uniquevalues)

    distance = {i : float("Inf") for i in uniquevalues}
    distance[source] = 0

    # Correction of the main bug: number of iterations corrected
    for i in range(num_nodes - 1):
        for source, dest, cost in graph:
            # No need to treat Infinity separately:
            if distance[source] + cost < distance[dest]:
                distance[dest] = distance[source] + cost

    for source, dest, cost in graph:
        # No need to treat Infinity separately:
        if distance[source] + cost < distance[dest]:
            print("Graph contains a negative-weight cycle")
            return None

    return distance

graph = [
    (1, 2, -2),
    (3, 1, 1),   # Corrected to represent a cycle
    (2, 3, -2),
]

shortest_path = bellman_ford(graph, 3)
print(shortest_path)

Answer 2

With trincot's clarification of my implementation not being bidirectional, I fixed my algorithm to check backwards as well to allow for alternate sources. This fixed my code and it now does exactly what I want it to do.