LeetCode. Cheapest Flights Within K Stops

Problem:

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, 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.

 

-Summary-

Using Dijkstra's Algorithm

 

-Debugging-

leetcode.com/problems/cheapest-flights-within-k-stops/discuss/267200/Python-Dijkstra

Python Dijkstra - LeetCode Discuss

이번 문제는 너무 이해가 안가서, discussion에서의 답을 보고 그대로 작성한 다음에 디버깅 해가며 이해를 할려고 노력했다. 마지막에 이해는 됬지만, 다음에는 discussion의 도움없이 혼자 풀수 있을때까지 더 열심히 노력해야겠다.

문제를 디버깅 해가며 아래와 같은 새로운 개념과 함수들을 배웠다.

 

Python Heap Data Structure - Heap data structure is mainly used to represent a priority queue

- import heapq: importing heap data structure

- heappush(heap, ele): This function is used to insert the element mentioned in its arguments into heap. The order is adjusted, so as heap structure is maintained.

- heappop(heap):- This function is used to remove and return the smallest element from heap. The order is adjusted, so as heap structure is maintained.

 

https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

Heap queue (or heapq) in Python - GeeksforGeeks

Python type defaultdict - alternative to dict that’s specifically designed to help you out with missing keys. defaultdict is a Python type that inherits from dict. (이거는 말 그대로 그냥 똑같은 dict 이지만, key 가 없을경우에 key error 로 빠지지 않고 dictionary default value로 initialize 해준다.)

 

https://realpython.com/python-defaultdict/#understanding-the-python-defaultdict-type

Using the Python defaultdict Type for Handling Missing Keys – Real Python

https://stackoverflow.com/questions/41455065/understanding-the-use-of-defaultdict-in-python

Understanding the use of defaultdict in Python

 

-Dijkstra Algorithm Animation

commons.wikimedia.org/wiki/File:Dijkstra_Animation.gif

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]