Ndtyjky

I am implementing a Bellman-ford shortest path algorithm. Based on the source and destination node, it outputs the shortest distance, and the path through a network.

Now, I need to add a capacity component to the algorithm. So if the demand is 2 but the capacity is 1, that path is no longer usable.

My initial idea was to add a dictionary for the capacity and a variable for the demand. Then if the demand exceeded the capacity of a node, the lenght of the path would be arbritrarily large. I was thinking something like:

           if capacity[neighbour] < demand:

                distance[neighbour], predecessor[neighbour] = 999

This gives me the following error message:

TypeError: '<' not supported between instances of 'dict' and 'int'

Is there a workaround for this issue, or could I potentially add the demand-constraint in a smarter way?

Full code:

source = 'e'

destination = 'd'

demand = 2



def bellman_ford(graph, source, capacity):

# Step 1: Prepare the distance and predecessor for each node

distance, predecessor = dict(), dict()



for node in capacity:

    for node in graph:

        distance[node], predecessor[node] = float('inf'), None

        distance[source] = 0



# Step 2: Relax the edges

for _ in range(len(graph) - 1):

    for node in graph:

        for neighbour in graph[node]:

            # If the distance between the node and the neighbour is lower than the current, store it

            if distance[neighbour] > distance[node] + graph[node][neighbour]:

                distance[neighbour], predecessor[neighbour] = distance[node] + graph[node][neighbour], node

            if capacity[node] < demand:

                distance[neighbour], predecessor[neighbour] = 100





# Step 3: Check for negative weight cycles

for node in graph:

    for neighbour in graph[node]:

        assert distance[neighbour] <= distance[node] + graph[node][neighbour], "Negative weight cycle."



return distance, predecessor



#Initial graph



graph = {

    'a': {'b': 1, 'd':  1},

    'b': {'c':  1, 'd':  2},

    'c': {},

    'd': {'b':  1, 'c':  8, 'e': 1},

    'e': {'a': 2, 'd': 7}

}





capacity = {

    'a': {'b': 4, 'd':  1},

    'b': {'c':  5, 'd':  4},

    'c': {},

    'd': {'b':  1, 'c':  3, 'e': 3},

    'e': {'a': 5, 'd': 3}

}





distance, predecessor = bellman_ford(graph, source, capacity)



print("The cost of shipping from from", source, "to", destination, "is", distance[destination])



for i in graph:

    print("node",i,"is reached through node", predecessor[i])