Negative cycles usually occur in weighted directed graphs. What then is a negative cycle? A negative cycle takes place when the total sum of the cycle in a graph is negative. Negative weights are required for these cycles to exist. It will be great to explore the meaning and scenarios of negative weights.
Negative weights of a graph:
In an earlier article, I touched on the different types of weights in a graph. We’ve got flow, capacity, frequency, distance, time, resistance and cost weights. Negative edges and cycles are not always common in graphs. Their existence determines the most suitable algorithm to either detect or print the negative cycle. Before looking into the best algorithmic implementation of the negative cycles in a graph, it will be great to explore some scenarios or examples of negative edges.
Logistics Example: Let’s assume you are a delivery driver contracting for an eCommerce company and the weight of your edges W(a,b,c) of an edge a,b,c is the cost of petrol or diesel from the depot to the customer destination. Nodes x,y,z form a negative cycle as these are last-minute delivery destinations that the contracting driver has just accepted from a different supplier.
Let’s assume the delivery driver is contracting for Amazon and node [a] is the amazon depot and the contractor is expected to drop off parcels to customers in nodes [b] and [c] respectively. An hour before leaving, the delivery driver receives a notification from a retailer he contracts for to deliver an item to two customer destinations. Let’s assume this retailer is known as Flywing. Due to the last-minute nature of this request, Flywing will reimburse the delivery driver with the cost of petrol in addition to a competitive delivery pay. The driver is expected to pick up the additional items from node [x] and deliver them to customers in nodes [y] and [z].
The weight of the above graph is the cost of petrol to the delivery driver. The positive weights express the petrol cost attributed to the delivery driver. While the negative weights are those that are to be reimbursed by the retailer. In simple terms, the delivery driver bears the cost when the weight is positive but the retailer is responsible for the cost when weights are negative. In this example, the cost of petrol will be 45p per mile for the first 100 miles and 25p per mile afterwards,
Negative weights are an interesting mathematical problem that can seamlessly be extended to other applications that are confronted with the shortest-path problems. We also aim to present a suitable algorithm that is well suited to handling the negative edge weight shortest path problem. When negative edge weights are introduced to a network it changes its complete dynamics and outlook. Sedgewick reminds us that when negative low-weight edges are present in a graph, the shortest path is likely to consist of more edges than the higher-weight path. This can be clearly seen from our graph above. The shortest path from a to c will consist of more edges due to the presence of negative weights. In this case, the shortest path from a to c will consist of six nodes and [a,x,y,z,b,c] the shortest path weight of 8. The shortest path traversal on a graph with solely positive weights prompts shortcuts while a network with negative weights results in detours.
Revisiting the earlier example, the delivery driver is avoiding the shortcut of [a,b,c] and embracing a detour [a,x,y,z,b,c] to include dropping off the last-minute items to the retailer
Bellman-Ford’s algorithm on negative weights and Python implementation
By way of reminder, a negative cycle is one in which the overall aggregate of the cycle becomes negative. There is a negative cycle in our example above as the nodes from the retailer [x,y,z] form a negative cycle. The Bellman-Ford algorithm is effective in ascertaining if a network has a negative cycle and printing where n.
We will run a python implementation that prints the below graph with supposedly a negative cycle. The code is sourced from
