• 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]],
 'C') == 70
cheapest_flight([['A', 'C', 100],
  ['A', 'B', 20],
  ['B', 'C', 50]],
 '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:
        for y,w in graph[dest].items():
            pq.put((minCost+w, y))
    return -1
solution(flights, src, dst)

2 Answers 2


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)

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

  • \$\begingroup\$ thanks for your comments. I will make the changes related to documentation and naming convention. Regarding functionality, I have changed while pq to while not pq.empty(). Do you see any other issue functionality wise? \$\endgroup\$
    – meallhour
    Oct 9, 2022 at 15:09
  • \$\begingroup\$ I have just now noticed that after changing the while loop, shortest_path(flights, "C", "A") is returning -1 which is not correct? \$\endgroup\$
    – meallhour
    Oct 9, 2022 at 16:20
  • \$\begingroup\$ Should I make two types of entries in the graph dict?. graph = defaultdict(dict) for s,d,w in flights: graph[s][d] = w for s,d,w in flights: graph[d][s] = w \$\endgroup\$
    – meallhour
    Oct 9, 2022 at 16:22
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – meallhour
    Oct 9, 2022 at 16:23
  • \$\begingroup\$ what do you think about adding an if condition inside the for loop? for neighbor, w in graph[dest].items(): if neighbor not in vis: pq.put((minCost+w, neighbor)) \$\endgroup\$
    – meallhour
    Oct 10, 2022 at 17:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.