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

CodePudding user response：

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

CodePudding user response：

While queueing neighbours, you're not checking if the neighbour is already visited. For example, after visiting b from a, you'll check the possibility where a is being visited again (basically a -> b -> a). Visiting the same node again in a path will never be optimal, so we can safely discard such possibilities.

Doing that is easy, you just need to maintain a set of nodes visited in the current path (using a set would allow faster lookups).

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

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