Graph in Leetcode
This section is to summarize my notes on solving graph problem, with visualization, thinking process, and references from lots of other solutions.
Cheapest Flight Price with K stops
The solution of this is to utilize Dijkstra shortest path to find the minimum cost from one source to destination. So the java solution is to utilize Priority Queue as mentioned in Dijkstra code.
The basic thought is convert the flights list to a graph with map or dictionary data structure, the solution is to utilize priority Queue, then pop each element, if the stops number less than K , then put the cost plus neighbor cost, stop plus one more city, update the source to the destination element. And return the cost when the retrieved city equal to destination.
So, the initialization of graph and queue are really important. The graph decided how to store the map with each city.
The queue decided the order of calculate each step with cost, and save each combination to the queue. Utile finally we found the last city of start which is equal to our destination, then it will be available to jump out the loop. The core thought is to utilize the Dijkstra method, like the cost is the weight between 2 cities, and to find the minimum cost which is…
