def find_cheapest_flight_no_heapq(flights, origin, destination):
# Initialize the queue with the starting airport and a cost of 0
queue = [(0, origin)]
# Dictionary to store the minimum cost to reach each airport
min_cost = {origin: 0}
# Process each airport in the queue
while queue:
# Find the element with the smallest cost in the queue
current_index = 0
for i in range(1, len(queue)):
if queue[i][0] < queue[current_index][0]: # Compare costs to find minimum
current_index = i
# Remove the element with the smallest cost from the queue
current_cost, current_airport = queue.pop(current_index)
# If the current airport is the destination, return the cost
if current_airport == destination:
return current_cost
# Iterate through all neighbors (connected airports)
for neighbor, price in flights.get(current_airport, {}).items():
# Calculate the new cost to reach the neighbor
new_cost = current_cost + price
# Update the minimum cost to reach the neighbor if it's cheaper
if new_cost < min_cost.get(neighbor, float('inf')):
min_cost[neighbor] = new_cost # Store the new minimum cost
queue.append((new_cost, neighbor)) # Add the neighbor to the queue
# If the destination is not reachable, return -1
return -1
# Example Input
flights = {
"JFK": {"LAX": 500, "ORD": 200}, # Flights from JFK to LAX and ORD with costs
"ORD": {"LAX": 300, "MIA": 150}, # Flights from ORD to LAX and MIA with costs
"LAX": {"MIA": 200}, # Flights from LAX to MIA with cost
"MIA": {"ATL": 100}, # Flights from MIA to ATL with cost
"ATL": {} # No outgoing flights from ATL
}
# Example Usage
origin = "JFK" # Starting airport
destination = "MIA" # Target airport
cheapest_price = find_cheapest_flight_no_heapq(flights, origin, destination)
# Print the result based on the output of the function
if cheapest_price != -1:
print(f"The cheapest flight from {origin} to {destination} costs ${cheapest_price}")
else:
print(f"No route found from {origin} to {destination}")
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter