- As the input you get the flight schedule as an array, each element of which is the price of a direct flight between 2 cities
(an array of 3 elements - 2 city names as a string, and a flight price).
- Planes fly in both directions and the price in both directions is the same. There is a possibility that there are no direct flights between cities.
Find the price of the cheapest flight between cities that are given as the 2nd and 3rd arguments.
3 arguments: the flight schedule as an array of arrays, city of departure and destination city.
Int. The best price.
cheapest_flight([['A', 'C', 100], ['A', 'B', 20], ['B', 'C', 50]], 'A', 'C') == 70 cheapest_flight([['A', 'C', 100], ['A', 'B', 20], ['B', 'C', 50]], 'C', 'A') == 70
I am using
Dijkstras Algorithm to resolve the problem.
Please let me know if this approach can be improved in any way.
flights = [['A', 'C', 100], ['A' ,'B', 20], ['B', 'C', 50]] src = "A" dst = "C" def solution(flights, src, dst): from collections import defaultdict from queue import PriorityQueue graph = defaultdict(dict) for s,d,w in flights: graph[s][d] = w pq = PriorityQueue() pq.put((0, src)) vis = set() while pq: minCost, dest = pq.get() if dest == dst: return minCost if dest in vis: continue vis.add(dest) for y,w in graph[dest].items(): pq.put((minCost+w, y)) return -1 solution(flights, src, dst)