Bug Report for cheapest-flight-path

[DiwashPatel]

Bug Report: Incorrect Handling of k Stops in Cheapest Flight Path (written using chatgpt)

Problem

The current solution for Cheapest Flight Path can incorrectly pass all the current test cases present in Neetcode because it updates distances in-place during each iteration.

This can allow the algorithm to use more than k stops in a single round of relaxation, which breaks the intended constraint.

Code

dist = {i: float("inf") for i in range(n)}
dist[src] = 0

for i in range(k + 1):
    for n1, n2, weight in flights[::-1]:
        if dist[n1] + weight < dist[n2]:
            dist[n2] = dist[n1] + weight

return dist[dst] if dist[dst] < float("inf") else -1

Test Case

n = 5
flights = [
    [1, 0, 5],
    [2, 1, 5],
    [3, 0, 2],
    [1, 3, 2],
    [4, 1, 1],
    [2, 4, 1]
]
src = 2
dst = 0
k = 2

Expected Behavior

The solution should respect the limit of at most k stops.

For this test case, paths that require more than k stops should not be considered valid.

Actual Behavior

The code may update distances too quickly within the same iteration because it modifies dist in-place.

For example, if the edges are processed in an order that starts from the source node, the algorithm can keep using newly updated distances in the same round. This makes it possible to count paths with too many stops.

Reversing the list of flights can make the code pass the current test cases, but this only works by accident. It seems the existing tests may not include a case where the source edge appears near the end of the list.

On LeetCode, the same approach fails (becz of course it's wrong).

Adding the test case above should catch this issue.