The below code for finding Cheapest Fare is giving "Time Limit Exceeded" for one test case

Question

Details:

• There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

• Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example1:

Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200

Example2:

Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500

My Code:

n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0
dst = 3
k = 1

def solution(n, flights, src, dst, k):
    from collections import defaultdict
    import heapq as hq
    
    graph = defaultdict(dict)
    for s, d, w in flights:
        graph[s][d] = w
    
    heap = [(0, src, k+1)]
    hq.heapify(heap)
    
    while heap:
        minCost, dest, redges = hq.heappop(heap)  #redges => remaining edges
        if redges>=0:
            if dest == dst: return minCost
            
        for neighbor, weight in graph[dest].items():
            if redges>=0:
                hq.heappush(heap, (minCost+weight, neighbor, redges-1))
        
    return -1

I am getting 700 which is correct result but it is failing with Time Limit Exceeded with below input.

Is there a way to introduce break in above code?

13
[[11,12,74],[1,8,91],[4,6,13],[7,6,39],[5,12,8],[0,12,54],[8,4,32],[0,11,4],[4,0,91],[11,7,64],[6,3,88],[8,5,80],[11,10,91],[10,0,60],[8,7,92],[12,6,78],[6,2,8],[4,3,54],[3,11,76],[3,12,23],[11,6,79],[6,12,36],[2,11,100],[2,5,49],[7,0,17],[5,8,95],[3,9,98],[8,10,61],[2,12,38],[5,7,58],[9,4,37],[8,6,79],[9,0,1],[2,3,12],[7,10,7],[12,10,52],[7,2,68],[12,2,100],[6,9,53],[7,4,90],[0,5,43],[11,2,52],[11,8,50],[12,4,38],[7,9,94],[2,7,38],[3,7,88],[9,12,20],[12,0,26],[10,5,38],[12,8,50],[0,2,77],[11,0,13],[9,10,76],[2,6,67],[5,6,34],[9,7,62],[5,3,67]]
10
1
10

Source

Answer 1

The problem is that your algorithm allows cycles. That increases the amount of possibilities immensly.

The original code needs almost 16 millions iteration to find the solution. The modification below cuts that down to about 30 thousands

We need to record the route, I added an item here:

heap = [(0, src, [src], k+1)]
#                ^^^^^

It could be a set (more efficient), but an ordered list gives you some information about the solution, like that in this case it is [10, 5, 8, 7, 4, 0, 12, 2, 11, 6, 3, 9]

Then avoid returning to any stop already visited on the route.

heap = [(0, src, [src], k+1)]
hq.heapify(heap)
   
while heap:
    minCost, dest, route, redges = hq.heappop(heap)  #redges => remaining edges
    if redges>=0:
        if dest == dst: return minCost

    for neighbor, weight in graph[dest].items():
        if redges>=0 and neighbor not in route:
            hq.heappush(heap, (minCost+weight, neighbor, route + [neighbor], redges-1))

Note: if redges>=0 could be probably >0