✅Day54| LeetCode 787. Cheapest Flights Within K Stops

🌟 Welcome to the Leetcode Daily Challenge Solution! 🚀



Embark on an intriguing journey through the realm of graph traversal and shortest path algorithms as we tackle the task of finding the cheapest price to reach a destination with limited stops. Brace yourself for an adventure through algorithmic ingenuity and optimization mastery.


🎯 Problem Overview:


Our mission is to find the cheapest price to reach the destination 'dst' from the source 'src' with at most 'k' stops, given a list of flights represented as a graph. We aim to devise an algorithm that efficiently computes and returns the cheapest price.


🚀 Algorithm Breakdown:


Create an adjacency list 'adj' to represent the graph, where each node is mapped to a vector of pairs containing the neighbor node and the price of the flight.
Initialize a vector 'dist' of size 'n' to store the minimum cost to reach each node from the source. Set the distance of the source node to 0 and initialize all other distances to INT_MAX.
Use a queue 'q' to perform breadth-first search (BFS) traversal of the graph. Each element in the queue represents a pair containing the current node and the total cost to reach that node.
Perform BFS until the queue is empty or the number of stops exceeds 'k'. In each iteration:
Dequeue a node and its distance from the front of the queue.
If the node has no outgoing flights, skip to the next iteration.
Iterate through the neighbors of the current node:
If the total cost to reach the neighbor via the current node is less than its current minimum cost, update its distance and enqueue it.
Return the minimum cost to reach the destination node 'dst' if it is reachable within 'k' stops; otherwise, return -1.
📊 Complexity Analysis:


Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges (flights) in the graph. Each node is visited once, and each edge is traversed once during BFS.
Space Complexity: O(V), where V is the number of vertices. Additional space is used for the adjacency list, distance array, and queue.


Delve into the intricacies of graph traversal and optimization as we unravel the solution together! Feel empowered to explore, modify, and deepen your understanding of efficient strategies for finding the cheapest price to reach a destination with limited stops. 🔗✨


Tags: #leetcode #leetcodedailychallenge #leetcodesolutions #dailyvlog #algorithmexplained #codingtutorial #programminglogic #codingchallenge #algorithm #graphtraversal #shortestpath #cheapestprice #limitedstops