This is the Cheapest Flights Within K Stops problem from leetcode.com:
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\$.
I have a naive implementation that fails on efficiency. I had a feeling this would happen, but I took this approach to implement my first ever iterative deepening depth first search (IDDFS). Since it fails on runtime, I don't know if my code is 100% valid from an implementation standpoint
My algorithm:
- Enumerate all paths of depth less than \$K + 1\$ using IDDFS, add to priority queue by path cost
- If the queue isn't empty, a path exists that makes at most \$K\$ stops, extract min from priority queue.
Obviously step 1 grows exponentially and isn't at all efficient.
What I would like help reviewing is whether my iterative deepening depth first search is from an implementation standpoint correct.
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int, K + 1 = max search depth, K + 2 = amount of visited nodes
:rtype: int
"""
from collections import defaultdict
import heapq
adj = defaultdict(list) # u : (v, cost)
for u,v,c in flights:
adj[u].append((v,c))
paths = [] # pqueue
def enumerateAllPaths(u, goal, visited, path, pathcost, depthLimit):
visited[u] = True
path.append(u)
if u == goal:
heapq.heappush(paths, (pathcost, len(path), path))
elif depthLimit == 0:
path.pop()
visited[u] = False
return
else:
for v,c in adj[u]:
if not visited[v]:
enumerateAllPaths(v, goal, visited, path, pathcost + c, depthLimit - 1)
path.pop()
visited[u] = False
visited = [False for s in range(len(n))]
path = []
enumerateAllPaths(src, dst, visited, path, 0, K + 1)
# (length of path, pathcost, path)
bestcost = 2**63 - 1 # best cost decreases if a better path is found
if paths:
pathcost, pathlen, path = heapq.heappop(paths)
bestcost = pathcost
if bestcost != 2**63 - 1:
return bestcost
else:
return -1