Find the cheapest flight to reach from source to destination

Question

• 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.

Question:

Find the price of the cheapest flight between cities that are given as the 2nd and 3rd arguments.

Input:

3 arguments: the flight schedule as an array of arrays, city of departure and destination city.

Output:

Int. The best price.

Example:

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

MyCode:

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)

Answer 1

Problem: Try solution(flights, "C", "A")
(Part of this problem: while pq: doesn't work as intended - while not pq.empty(): should be closer.)

---

You present one slick implementation of Dijkstra's Algorithm.

This being CR, I think there are possible improvements to details of how it is coded - and one strategic one:

• Stick to the Style Guide for Python Code.
  Where deviating (like importing inside a function), have a reason to, maybe document that reason with a comment. Strategically

• Document your code. In the code.

• Naming:
  Name things for their role/purpose, not for their type.
  costs rather than graph, cheapest rather than pq.
  As code is read much more often than it is written, I'd prefer visited over vis.
  (And yes, there are variables here that are more difficult to name -
  code the way you think about the solution.)
  (I guess I'm inconsistent with this advice when inclined to name the function dijktra_s() rather than shortest_path().
  I do detest solution - make it an alias where needed.)

• You conditionally don't process some items found cheapest.
  Instead, make insertion conditional - unless evaluating that condition uses more resources than inserting in cheapest.

• to have the module usable from outside, put "usage examples" in a
  if __name__ == "__main__":

• Separation of concerns:
  I think transforming the flights array into a cost graph not to be part of Dijkstra's.
  I didn't come up with a better remedy to the "symmetry problem" mentioned at the start of this post than to add costs[d][s] = c (graph[d][s] = w) - yet.

• keep introduction of things close to usage, scopes small (even where only conceptual/"visual"):
  e.g., "the global" flights close to calls using it
  (When trying to do that with "the global src/dst", their motivation looks slim)

---

Algorithm:
Cost/distance being symmetrical, bidirectional Dijkstra's can be expected to use less resources.

Answer 2

Keep in mind that the queue library is designed to be thread safe. There is some extra overhead, such as for acquiring a mutex, before many operations. According to the documentation PriorityQueue is implemented using the heapq library. If thread safety isn't needed, consider using heapq directly.