Minimum Transportation Cost (Negative Cycles, Bellman-Ford)¶

Edited by Charles

Medium · Python · Graph

Problem

A country wants to promote economic exchange between cities by providing subsidies for cargo transportation.

There are n cities numbered from 1 to n. The cities are connected by a network of directed roads, meaning that a road from city u to city v cannot necessarily be traveled in the opposite direction.

Each road has a transportation cost and a government subsidy. The final weight of a road is calculated as:

Weight = Transportation Cost - Government Subsidy

A positive weight means that transportation still costs money after applying the government subsidy.

A negative weight means that the government subsidy exceeds the transportation cost, so traveling along that road actually generates a profit.

However, the road network may contain negative-weight cycles.

A negative-weight cycle is a cycle whose total edge weight is negative. By repeatedly traveling through such a cycle, the total transportation cost can theoretically be reduced indefinitely.

Your task is to find the minimum transportation cost from city 1 to city n, while also detecting whether a negative-weight cycle exists.

It is also possible that city n cannot be reached from city 1.

Function Signature¶

class Solution:
    def minimumCost(self, n: int, roads: List[List[int]]):

Parameters¶

`n`¶

The number of cities.

Cities are numbered:

1, 2, 3, ..., n

City 1 is the starting city.

City n is the destination.

`roads`¶

roads[i] = [u, v, w] represents a directed road from city u to city v with weight w.

u --w--> v

The weight w may be:

Positive
Zero
Negative

Return Value¶

Return the minimum transportation cost from city 1 to city n if a valid minimum cost exists.

If the minimum cost is negative, it represents the amount of profit generated after government subsidies.

If a negative-weight cycle is detected, return:

"circle"

If city n cannot be reached from city 1, return:

"unconnected"

Example 1¶

Input¶

n = 4

roads = [
    [1, 2, -1],
    [2, 3, 1],
    [3, 1, -1],
    [3, 4, 1]
]

Output¶

"circle"

Example 2¶

Input¶

n = 6

roads = [
    [5, 6, -2],
    [1, 2, 1],
    [5, 3, 1],
    [2, 5, 2],
    [2, 4, -3],
    [4, 6, 4],
    [1, 3, 5]
]

Output¶

Example 3¶

Input¶

n = 4

roads = [
    [1, 2, 2],
    [2, 3, -1]
]

Output¶

"unconnected"

Constraints¶

2 <= n
1 <= len(roads)
roads[i] = [u, v, w]
1 <= u, v <= n
The graph is directed.
Edge weights may be positive, zero, or negative.
The graph may contain negative-weight cycles.
Multiple paths may exist between two cities.
City n may be unreachable from city 1.

Explanation, examples & other approaches

Core idea

Bellman-Ford is a shortest-path algorithm that can handle:

Positive edge weights
Zero edge weights
Negative edge weights

Original study notes follow, including intermediate snippets and earlier attempts.

Approach: Bellman-Ford + Negative Cycle Detection¶

Bellman-Ford is a shortest-path algorithm that can handle:

Positive edge weights
Zero edge weights
Negative edge weights

Unlike Dijkstra, Bellman-Ford does not require all edge weights to be non-negative.

The core operation is relaxation.

For every edge:

u --w--> v

if:

minCost[u] + w < minCost[v]

then going from city 1 to u, followed by the edge u → v, gives us a cheaper path to v.

Therefore we update:

minCost[v] = minCost[u] + w

Define `minCost`¶

Let:

minCost[i]

represent:

The minimum transportation cost currently known from city 1 to city i.

Initially:

minCost = [float('inf')] * (n + 1)

Since the cost of traveling from city 1 to itself is 0:

minCost[1] = 0

So initially:

City:       1    2    3    ...    n
minCost:    0    ∞    ∞    ...    ∞

Relax Every Edge¶

Suppose we have an edge:

u --w--> v

If city u is already reachable from city 1, then the cost of reaching v through u is:

minCost[u] + w

If this is smaller than the current:

minCost[v]

we update it:

if (
    minCost[u] != float('inf')
    and minCost[v] > minCost[u] + w
):
    minCost[v] = minCost[u] + w

The condition:

minCost[u] != float('inf')

is important because we can only use the edge:

u → v

if city u is reachable from city 1.

Why Relax `n - 1` Times?¶

There are n cities.

If there is no negative cycle, a shortest path does not need to repeatedly visit the same node.

Therefore, a shortest simple path can contain at most:

n nodes

which means it can contain at most:

n - 1 edges

For example:

1 → 3 → 5 → 2 → 6

If there are 5 nodes on the path, there are 4 edges.

Therefore Bellman-Ford performs:

for _ in range(n - 1):

iterations.

During each iteration, we scan every edge and try to relax it.

Important Note About the `n - 1` Iterations¶

In this implementation, minCost is updated in place.

This means a newly updated distance may immediately be used by another edge later in the same iteration.

For example, if the edge order is:

1 → 2
2 → 3
3 → 4

then during just one scan:

1 → 2
    ↓
update 2

2 → 3
    ↓
use the new value of 2
    ↓
update 3

3 → 4
    ↓
use the new value of 3
    ↓
update 4

So one iteration may propagate information across multiple edges.

Therefore:

n - 1 is a safe upper bound on the number of full edge scans required.

It does not necessarily mean that exactly one additional edge is processed per iteration.

Why Can Bellman-Ford Detect Negative Cycles?¶

This is the most important part of this problem.

If there is no negative cycle, after enough relaxations, all shortest distances eventually become stable.

After performing:

n - 1

full scans of all edges, there should be no edge that can produce a smaller distance.

In other words, normally:

minCost[u] + w >= minCost[v]

for every reachable edge.

But suppose after n - 1 iterations we scan all edges one more time and still find:

minCost[u] + w < minCost[v]

Then the shortest distance is still decreasing.

That means some path is able to repeatedly reduce its total cost.

This can only happen because there is a reachable negative-weight cycle.

Example of a Negative Cycle¶

Consider:

1 --(-1)--> 2
2 --( 1)--> 3
3 --(-1)--> 1

The total cost of the cycle is:

-1 + 1 - 1 = -1

Every time we travel around this cycle, the total cost decreases by 1.

For example:

Start:

cost = 0

After one cycle:

cost = -1

After two cycles:

cost = -2

After three cycles:

cost = -3

...

Therefore the minimum cost has no lower bound.

It can continue decreasing forever.

Detect the Negative Cycle¶

After the normal n - 1 Bellman-Ford iterations, scan every edge one additional time:

for u, v, w in roads:

If any edge can still be relaxed:

if (
    minCost[u] != float('inf')
    and minCost[v] > minCost[u] + w
):

then return:

"circle"

The structure is:

Relax all edges n - 1 times
        ↓
Scan all edges one more time
        ↓
Can any edge still be relaxed?
       ↙            ↘
     Yes             No
      ↓               ↓
negative cycle     continue
      ↓
  "circle"

Why Check `minCost[u] != inf` When Detecting a Cycle?¶

Consider a negative cycle that exists somewhere else in the graph:

1 → 2 → n

5 → 6
↑   ↓
└── 7

Suppose:

5 → 6 → 7 → 5

is a negative cycle, but city 1 cannot reach cities 5, 6, or 7.

Then this negative cycle has no effect on paths starting from city 1.

Because:

minCost[5] == inf
minCost[6] == inf
minCost[7] == inf

the condition:

minCost[u] != float('inf')

prevents these unreachable edges from being considered.

Therefore, this implementation detects:

Negative cycles that are reachable from city 1.

Final Answer¶

If no reachable negative cycle is found, check:

minCost[n]

If:

minCost[n] == float('inf')

then city n cannot be reached from city 1.

Return:

"unconnected"

Otherwise:

return minCost[n]

Bellman-Ford Process Summary¶

Initialize minCost
        ↓
minCost[1] = 0
        ↓
Repeat n - 1 times
        ↓
Scan every edge
        ↓
Try relaxation
        ↓
After n - 1 iterations
        ↓
Scan every edge one more time
        ↓
Can any edge still be relaxed?
      ↙               ↘
    Yes                No
     ↓                  ↓
"circle"         Check minCost[n]
                  ↙           ↘
                inf         finite
                 ↓             ↓
         "unconnected"    minCost[n]

Bellman-Ford vs Dijkstra¶

Dijkstra¶

Dijkstra requires:

All edge weights >= 0

Once a node is finalized, its shortest distance will never change again.

Bellman-Ford¶

Bellman-Ford allows:

Negative edge weights

A node's shortest distance may decrease multiple times.

Therefore Bellman-Ford repeatedly relaxes edges until the distances become stable.

Bellman-Ford vs SPFA¶

Bellman-Ford scans:

ALL edges

during every iteration.

Its basic structure is:

repeat n - 1 times:
    scan every edge

SPFA instead uses a queue and mainly processes nodes whose distances have changed:

distance decreases
       ↓
put node into queue
       ↓
process its outgoing edges

So SPFA can avoid some unnecessary edge scans in practice.

However, both algorithms have the same worst-case time complexity:

O(VE)

Complexity¶

Let:

V = n
E = len(roads)

Time Complexity¶

Bellman-Ford performs up to:

V - 1

iterations.

Each iteration scans:

edges.

The additional negative-cycle check also scans E edges.

Therefore:

O(VE)

Space Complexity¶

We only need:

minCost

which contains V values.

Therefore:

O(V)

No adjacency list is required because Bellman-Ford can directly iterate over the edge list.

Key Takeaways¶

Relaxation¶

For an edge:

u --w--> v

try:

minCost[v] = min(
    minCost[v],
    minCost[u] + w
)

Why `n - 1`?¶

A shortest simple path in a graph with n nodes contains at most:

n - 1 edges

Negative Cycle Detection¶

The most important rule to remember is:

Relax edges for n - 1 iterations, then scan all edges one more time.

If an edge can still be relaxed:

distance can still decrease
        ↓
negative cycle exists

A useful memory shortcut is:

n - 1 passes → shortest paths
1 extra pass → negative cycle detection

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 1, 2026

Python solution¶

from typing import List

class Solution:
    def minimumCost(self, n: int, roads: List[List[int]]):
        minCost = [float('inf')] * (n + 1)
        minCost[1] = 0

        for _ in range(n - 1):
            for u, v, w in roads:
                if (
                    minCost[u] != float('inf')
                    and minCost[v] > minCost[u] + w
                ):
                    minCost[v] = minCost[u] + w

        # One more iteration to detect a negative cycle
        for u, v, w in roads:
            if (
                minCost[u] != float('inf')
                and minCost[v] > minCost[u] + w
            ):
                return 'circle'

        return 'unconnected' if minCost[n] == float('inf') else minCost[n]

Back to Day 54 Graph XII · All Algorithm notes

Minimum Transportation Cost (Negative Cycles, Bellman-Ford)¶

Function Signature¶

Parameters¶

n¶

roads¶

Return Value¶

Example 1¶

Input¶

Output¶

Example 2¶

Input¶

Output¶

Example 3¶

Input¶

Output¶

Constraints¶

Approach: Bellman-Ford + Negative Cycle Detection¶

Define minCost¶

Relax Every Edge¶

Why Relax n - 1 Times?¶

Important Note About the n - 1 Iterations¶

Why Can Bellman-Ford Detect Negative Cycles?¶

Example of a Negative Cycle¶

Detect the Negative Cycle¶

Why Check minCost[u] != inf When Detecting a Cycle?¶

Final Answer¶

Bellman-Ford Process Summary¶

Bellman-Ford vs Dijkstra¶

Dijkstra¶

Bellman-Ford¶

Bellman-Ford vs SPFA¶

Complexity¶

Time Complexity¶

Space Complexity¶

Key Takeaways¶

Relaxation¶

Why n - 1?¶

Negative Cycle Detection¶

Python solution¶

`n`¶

`roads`¶

Define `minCost`¶

Why Relax `n - 1` Times?¶

Important Note About the `n - 1` Iterations¶

Why Check `minCost[u] != inf` When Detecting a Cycle?¶

Why `n - 1`?¶