Graph Theory37 sections · 1633 units
Open in Course

Application: Network Routing

(Handling link costs)

In networks, some links might have negative costs, representing cash-back incentives, subsidized routes, or promotional discounts. Dijkstra fails here because it assumes costs are non-negative. Bellman-Ford correctly finds cheapest paths and detects if infinite profit loops exist.

This applies to any domain where costs can be negative: shipping networks with rebates, logistics with subsidies, financial systems with bonuses. Bellman-Ford handles all these cases correctly.