Jupyter Notebook · Graph Theory

Flight Optimization

Cost-optimal routing across 12 international airports modeled as a NetworkX graph. Dijkstra finds the cheapest path, Bellman-Ford validates costs and detects negative-weight cycles, and Basemap draws the route maps.

Installation and Import of Packages

In [1]:

import heapq
import networkx as nx
import matplotlib.pyplot as plt
import timeit
import matplotlib.pyplot as plt
from mpl_toolkits.basemap import Basemap
import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
from collections import deque
import time
import psutil
import time

Building Graph for Intra Airport Prices Points

In [2]:

class Graph:
    def __init__(self):
        # The graph is represented as an adjacency list
        self.graph = {}

    def add_node(self, node):
        # Add a new node to the graph
        if node not in self.graph:
            self.graph[node] = []

    def add_edge(self, source, destination, weight):
        # Add a directed edge with a weight from the source to the destination
        self.add_node(source)
        self.add_node(destination)
        self.graph[source].append((destination, weight))

    def __str__(self):
        # Display the graph as a string for easy visualization
        result = ""
        for node, neighbors in self.graph.items():
            result += f"{node}: {neighbors}\n"
        return result

    def visualize_path(self, path, title):
        G = nx.DiGraph()

        for node, neighbors in self.graph.items():
            G.add_node(node)
            for neighbor, weight in neighbors:
                G.add_edge(node, neighbor, weight=weight)

        pos = nx.spring_layout(G)
        edge_labels = {(node, neighbor): weight for node, neighbors in self.graph.items() for neighbor, weight in neighbors}

        nx.draw_networkx(G, pos, font_weight='bold', node_size=500, node_color='skyblue', font_color='black', font_size=3, edge_color='gray', width=1.5)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='red', node_size=500)
        nx.draw_networkx_labels(G, pos)
        plt.title(title)
        plt.show()



    def bfs(self, start, end):
        visited = set()
        queue = deque([(start, [start])])

        while queue:
            current_node, path = queue.popleft()

            if current_node == end:
                return path

            if current_node not in visited:
                visited.add(current_node)
                for neighbor, _ in self.graph[current_node]:
                    queue.append((neighbor, path + [neighbor]))

        return []
    
    def dfs(self, start, end, visited=None, path=None):
        if visited is None:
            visited = set()
        if path is None:
            path = []

        visited.add(start)
        path = path + [start]

        if start == end:
            # Visualize the path if the destination is reached
            self.visualize_path(path, 'Shortest Path (Depth-First Search)')
            return path

        for neighbor, _ in self.graph[start]:
            if neighbor not in visited:
                new_path = self.dfs(neighbor, end, visited, path)
                if new_path:
                    return new_path

        return []
    
    def bellman_ford(self, start, end):
        # Initialize distances from the start node to all other nodes as infinity
        distance = {node: float('inf') for node in self.graph}
        distance[start] = 0
        predecessor = {node: None for node in self.graph}

        # Relax edges repeatedly
        for _ in range(len(self.graph) - 1):
            for node in self.graph:
                for neighbor, weight in self.graph[node]:
                    if distance[node] + weight < distance[neighbor]:
                        distance[neighbor] = distance[node] + weight
                        predecessor[neighbor] = node

        # Check for negative weight cycles
        for node in self.graph:
            for neighbor, weight in self.graph[node]:
                if distance[node] + weight < distance[neighbor]:
                    raise ValueError("Graph contains a negative weight cycle")

        # Reconstruct the shortest path
        path = [end]
        while predecessor[end] is not None:
            path.insert(0, predecessor[end])
            end = predecessor[end]

        # Return the shortest path and its distance
        return path, distance[end]


    def dijkstra(self, start, end):
        # Priority queue to store (distance, node) pairs
        priority_queue = [(0, start)]

        # Dictionary to store the distance from start to each node
        distance = {node: float('infinity') for node in self.graph}
        distance[start] = 0

        # Dictionary to store the previous node in the shortest path
        previous = {node: None for node in self.graph}

        while priority_queue:
            current_distance, current_node = heapq.heappop(priority_queue)

            # If the current node is the destination, reconstruct the path
            if current_node == end:
                path = []
                while previous[current_node] is not None:
                    path.insert(0, current_node)
                    current_node = previous[current_node]
                path.insert(0, start)

                # Visualize the shortest path
                #self.visualize_path(path, 'Shortest Path (Dijkstra\'s Algorithm)')
                return path, distance[end]

            # Explore neighbors
            for neighbor, edge_weight in self.graph[current_node]:
                new_distance = current_distance + edge_weight

                # Update distance and previous node if a shorter path is found
                if new_distance < distance[neighbor]:
                    distance[neighbor] = new_distance
                    previous[neighbor] = current_node
                    heapq.heappush(priority_queue, (new_distance, neighbor))

        # If no path is found
        return [], float('infinity')

# Example usage:
g = Graph()

# Adding nodes
g.add_node('DEL')
g.add_node('CDG')
g.add_node('IST')
g.add_node('LHR')
g.add_node('AMS')
g.add_node('JFK')
g.add_node('NRT')
g.add_node('SYD')
g.add_node('LAX')
g.add_node('ZLO')
g.add_node('DXB')
g.add_node('SIN')


g.add_edge('DEL', 'CDG', weight=655)
g.add_edge('DEL', 'IST', weight=479)
g.add_edge('DEL', 'LHR', weight=761)
g.add_edge('DEL', 'AMS', weight=660)
g.add_edge('DEL', 'JFK', weight=998)
g.add_edge('DEL', 'NRT', weight=384)
g.add_edge('DEL', 'SYD', weight=534)
g.add_edge('DEL', 'LAX', weight=1033)
g.add_edge('DEL', 'ZLO', weight=2026)
g.add_edge('DEL', 'DXB', weight=277)
g.add_edge('DEL', 'SIN', weight=250)

g.add_edge('CDG', 'IST', weight=219)
g.add_edge('CDG', 'LHR', weight=118)
g.add_edge('CDG', 'AMS', weight=144)
g.add_edge('CDG', 'JFK', weight=395)
g.add_edge('CDG', 'NRT', weight=666)
g.add_edge('CDG', 'SYD', weight=855)
g.add_edge('CDG', 'LAX', weight=553)
g.add_edge('CDG', 'ZLO', weight=2070)
g.add_edge('CDG', 'DXB', weight=406)
g.add_edge('CDG', 'SIN', weight=885)

g.add_edge('IST', 'LHR', weight=220)
g.add_edge('IST', 'AMS', weight=298)
g.add_edge('IST', 'JFK', weight=733)
g.add_edge('IST', 'NRT', weight=857)
g.add_edge('IST', 'SYD', weight=844)
g.add_edge('IST', 'LAX', weight=613)
g.add_edge('IST', 'ZLO', weight=1397)
g.add_edge('IST', 'DXB', weight=305)
g.add_edge('IST', 'SIN', weight=495)

g.add_edge('LHR', 'AMS', weight=156)
g.add_edge('LHR', 'JFK', weight=448)
g.add_edge('LHR', 'NRT', weight=580)
g.add_edge('LHR', 'SYD', weight=709)
g.add_edge('LHR', 'LAX', weight=569)
g.add_edge('LHR', 'ZLO', weight=1098)
g.add_edge('LHR', 'DXB', weight=495)
g.add_edge('LHR', 'SIN', weight=703)

g.add_edge('AMS', 'JFK', weight=546)
g.add_edge('AMS', 'NRT', weight=1089)
g.add_edge('AMS', 'SYD', weight=711)
g.add_edge('AMS', 'LAX', weight=651)
g.add_edge('AMS', 'ZLO', weight=1508)
g.add_edge('AMS', 'DXB', weight=503)
g.add_edge('AMS', 'SIN', weight=779)

g.add_edge('JFK', 'NRT', weight=1052)
g.add_edge('JFK', 'SYD', weight=1339)
g.add_edge('JFK', 'LAX', weight=329)
g.add_edge('JFK', 'ZLO', weight=338)
g.add_edge('JFK', 'DXB', weight=755)
g.add_edge('JFK', 'SIN', weight=959)

g.add_edge('NRT', 'SYD', weight=435)
g.add_edge('NRT', 'LAX', weight=614)
g.add_edge('NRT', 'ZLO', weight=3874)
g.add_edge('NRT', 'DXB', weight=689)
g.add_edge('NRT', 'SIN', weight=289)

g.add_edge('SYD', 'LAX', weight=808)
g.add_edge('SYD', 'ZLO', weight=2293)
g.add_edge('SYD', 'DXB', weight=771)
g.add_edge('SYD', 'SIN', weight=310)

g.add_edge('LAX', 'ZLO', weight=356)
g.add_edge('LAX', 'DXB', weight=850)
g.add_edge('LAX', 'SIN', weight=975)

g.add_edge('ZLO', 'DXB', weight=1536)
g.add_edge('ZLO', 'SIN', weight=2922)

g.add_edge('DXB', 'SIN', weight=586)

g.add_edge('CDG', 'DEL', weight=655)
g.add_edge('IST', 'DEL', weight=479)
g.add_edge('LHR', 'DEL', weight=761)
g.add_edge('AMS', 'DEL', weight=660)
g.add_edge('JFK', 'DEL', weight=998)
g.add_edge('NRT', 'DEL', weight=384)
g.add_edge('SYD', 'DEL', weight=534)
g.add_edge('LAX', 'DEL', weight=1033)
g.add_edge('ZLO', 'DEL', weight=2026)
g.add_edge('DXB', 'DEL', weight=277)
g.add_edge('SIN', 'DEL', weight=250)

g.add_edge('IST', 'CDG', weight=219)
g.add_edge('LHR', 'CDG', weight=118)
g.add_edge('AMS', 'CDG', weight=144)
g.add_edge('JFK', 'CDG', weight=395)
g.add_edge('NRT', 'CDG', weight=666)
g.add_edge('SYD', 'CDG', weight=855)
g.add_edge('LAX', 'CDG', weight=553)
g.add_edge('ZLO', 'CDG', weight=2070)
g.add_edge('DXB', 'CDG', weight=406)
g.add_edge('SIN', 'CDG', weight=885)

g.add_edge('LHR', 'IST', weight=220)
g.add_edge('AMS', 'IST', weight=298)
g.add_edge('JFK', 'IST', weight=733)
g.add_edge('NRT', 'IST', weight=857)
g.add_edge('SYD', 'IST', weight=844)
g.add_edge('LAX', 'IST', weight=613)
g.add_edge('ZLO', 'IST', weight=1397)
g.add_edge('DXB', 'IST', weight=305)
g.add_edge('SIN', 'IST', weight=495)

g.add_edge('AMS', 'LHR', weight=156)
g.add_edge('JFK', 'LHR', weight=448)
g.add_edge('NRT', 'LHR', weight=580)
g.add_edge('SYD', 'LHR', weight=709)
g.add_edge('LAX', 'LHR', weight=569)
g.add_edge('ZLO', 'LHR', weight=1098)
g.add_edge('DXB', 'LHR', weight=495)
g.add_edge('SIN', 'LHR', weight=703)

g.add_edge('JFK', 'AMS', weight=546)
g.add_edge('NRT', 'AMS', weight=1089)
g.add_edge('SYD', 'AMS', weight=711)
g.add_edge('LAX', 'AMS', weight=651)
g.add_edge('ZLO', 'AMS', weight=1508)
g.add_edge('DXB', 'AMS', weight=503)
g.add_edge('SIN', 'AMS', weight=779)

g.add_edge('NRT', 'JFK', weight=1052)
g.add_edge('SYD', 'JFK', weight=1339)
g.add_edge('LAX', 'JFK', weight=329)
g.add_edge('ZLO', 'JFK', weight=338)
g.add_edge('DXB', 'JFK', weight=755)
g.add_edge('SIN', 'JFK', weight=959)

g.add_edge('SYD', 'NRT', weight=435)
g.add_edge('LAX', 'NRT', weight=614)
g.add_edge('ZLO', 'NRT', weight=3874)
g.add_edge('DXB', 'NRT', weight=689)
g.add_edge('SIN', 'NRT', weight=289)

g.add_edge('LAX', 'SYD', weight=808)
g.add_edge('ZLO', 'SYD', weight=2293)
g.add_edge('DXB', 'SYD', weight=771)
g.add_edge('SIN', 'SYD', weight=310)

g.add_edge('ZLO', 'LAX', weight=356)
g.add_edge('DXB', 'LAX', weight=850)
g.add_edge('SIN', 'LAX', weight=975)

g.add_edge('DXB', 'ZLO', weight=1536)
g.add_edge('SIN', 'ZLO', weight=2922)

g.add_edge('SIN', 'DXB', weight=586)

print(g)

DEL: [('CDG', 655), ('IST', 479), ('LHR', 761), ('AMS', 660), ('JFK', 998), ('NRT', 384), ('SYD', 534), ('LAX', 1033), ('ZLO', 2026), ('DXB', 277), ('SIN', 250)]
CDG: [('IST', 219), ('LHR', 118), ('AMS', 144), ('JFK', 395), ('NRT', 666), ('SYD', 855), ('LAX', 553), ('ZLO', 2070), ('DXB', 406), ('SIN', 885), ('DEL', 655)]
IST: [('LHR', 220), ('AMS', 298), ('JFK', 733), ('NRT', 857), ('SYD', 844), ('LAX', 613), ('ZLO', 1397), ('DXB', 305), ('SIN', 495), ('DEL', 479), ('CDG', 219)]
LHR: [('AMS', 156), ('JFK', 448), ('NRT', 580), ('SYD', 709), ('LAX', 569), ('ZLO', 1098), ('DXB', 495), ('SIN', 703), ('DEL', 761), ('CDG', 118), ('IST', 220)]
AMS: [('JFK', 546), ('NRT', 1089), ('SYD', 711), ('LAX', 651), ('ZLO', 1508), ('DXB', 503), ('SIN', 779), ('DEL', 660), ('CDG', 144), ('IST', 298), ('LHR', 156)]
JFK: [('NRT', 1052), ('SYD', 1339), ('LAX', 329), ('ZLO', 338), ('DXB', 755), ('SIN', 959), ('DEL', 998), ('CDG', 395), ('IST', 733), ('LHR', 448), ('AMS', 546)]
NRT: [('SYD', 435), ('LAX', 614), ('ZLO', 3874), ('DXB', 689), ('SIN', 289), ('DEL', 384), ('CDG', 666), ('IST', 857), ('LHR', 580), ('AMS', 1089), ('JFK', 1052)]
SYD: [('LAX', 808), ('ZLO', 2293), ('DXB', 771), ('SIN', 310), ('DEL', 534), ('CDG', 855), ('IST', 844), ('LHR', 709), ('AMS', 711), ('JFK', 1339), ('NRT', 435)]
LAX: [('ZLO', 356), ('DXB', 850), ('SIN', 975), ('DEL', 1033), ('CDG', 553), ('IST', 613), ('LHR', 569), ('AMS', 651), ('JFK', 329), ('NRT', 614), ('SYD', 808)]
ZLO: [('DXB', 1536), ('SIN', 2922), ('DEL', 2026), ('CDG', 2070), ('IST', 1397), ('LHR', 1098), ('AMS', 1508), ('JFK', 338), ('NRT', 3874), ('SYD', 2293), ('LAX', 356)]
DXB: [('SIN', 586), ('DEL', 277), ('CDG', 406), ('IST', 305), ('LHR', 495), ('AMS', 503), ('JFK', 755), ('NRT', 689), ('SYD', 771), ('LAX', 850), ('ZLO', 1536)]
SIN: [('DEL', 250), ('CDG', 885), ('IST', 495), ('LHR', 703), ('AMS', 779), ('JFK', 959), ('NRT', 289), ('SYD', 310), ('LAX', 975), ('ZLO', 2922), ('DXB', 586)]

In [3]:

locations = {
    "DEL": {"latitude": 28.7041, "longitude": 77.1025, "name": "Delhi"},
    "IST": {"latitude": 41.0082, "longitude": 28.9784, "name": "Istanbul"},
    "CDG": {"latitude": 48.8566, "longitude": 2.3522, "name": "Paris"},
    "LHR": {"latitude": 51.5074, "longitude": -0.1278, "name": "London"},
    "AMS": {"latitude": 52.3676, "longitude": 4.9041, "name": "Amsterdam"},
    "JFK": {"latitude": 40.7128, "longitude": -74.0060, "name": "New York City"},
    "NRT": {"latitude": 35.6895, "longitude": 139.6917, "name": "Tokyo"},
    "SYD": {"latitude": -33.8688, "longitude": 151.2093, "name": "Sydney"},
    "LAX": {"latitude": 33.9416, "longitude": -118.4085, "name": "Los Angeles"},
    "ZLO": {"latitude": 19.1448, "longitude": -104.5586, "name": "Manzanillo"},
    "DXB": {"latitude": 25.2048, "longitude": 55.2708, "name": "Dubai"},
    "SIN": {"latitude": 1.3521, "longitude": 103.8198, "name": "Singapore"}
}

Djikstra's Algorithm

In [4]:

def fig2img(fig):
    """Convert a Matplotlib figure to a PIL Image and return it"""
    import io
    buf = io.BytesIO()
    fig.savefig(buf)
    buf.seek(0)
    img = Image.open(buf)
    return img

# Get the current memory usage
def get_memory_usage():
    process = psutil.Process()
    return process.memory_info().rss / 1024  # Memory usage in kilobytes


def find_cheapest_path(start_location,end_location):
    start_location = start_location
    end_location = end_location

    start_time = time.time()
    shortest_path, total_weight = g.dijkstra(start_location, end_location)
    end_time = time.time()
    # Display the result
    print(f"Cheapest Path from {start_location} to {end_location}: {shortest_path}")
    print(f"Total Price: {total_weight}$")
    print("Execution time: ", end_time-start_time)
    memory_used = get_memory_usage()

    print("Memory used:", memory_used, "kilobytes")


    plt.figure(figsize=(12, 8))

    # Create Basemap instance
    map = Basemap()

    # Draw coastlines
    map.drawcoastlines(linewidth=1.5)

    # Draw countries with filled colors
    map.drawcountries()


    prev_lat = None
    prev_long = None

    for country in shortest_path:
        cont_lat, cont_lon = locations[country]["latitude"], locations[country]["longitude"]
        x_cont, y_cont = map(cont_lon, cont_lat)
        map.plot(x_cont, y_cont, 'ro', markersize=6)
        plt.text(x_cont, y_cont, locations[country]["name"], fontsize=13, ha='left',fontweight='bold', color='blue')

        if prev_lat == None and prev_long == None:
            prev_lat = cont_lat
            prev_long = cont_lon

        else:
            map.drawgreatcircle(cont_lon, cont_lat, prev_long, prev_lat, linewidth=2, color='green')
            prev_lat = cont_lat
            prev_long = cont_lon



    # Show the map

    plt.title('Cheapest Flight route costs about ' + str(total_weight) + '$ using path given below.')
    return fig2img(plt)

In [5]:

path_dfs = g.dfs('DEL', 'SIN')
print("DFS Path:", path_dfs)

DFS Path: ['DEL', 'CDG', 'IST', 'LHR', 'AMS', 'JFK', 'NRT', 'SYD', 'LAX', 'ZLO', 'DXB', 'SIN']

In [6]:

import time
import psutil

# Get the current memory usage
def get_memory_usage():
    process = psutil.Process()
    return process.memory_info().rss / 1024  # Memory usage in kilobytes

# Your code
start_time = time.time()

# Assuming g.bfs() returns the path
start_node = 'SIN'
end_node = 'ZLO'
shortest_path, shortest_distance = g.bellman_ford(start_node, end_node)
print("Shortest path from", start_node, "to", end_node, ":", shortest_path)

end_time = time.time()

# Calculate the time taken
elapsed_time = end_time - start_time

# Get the memory usage after executing the code
memory_used = get_memory_usage()


print("Time taken:", elapsed_time, "seconds")
print("Memory used:", memory_used, "kilobytes")

Shortest path from SIN to ZLO : ['SIN', 'NRT', 'LAX', 'ZLO']
Time taken: 0.00020003318786621094 seconds
Memory used: 105472.0 kilobytes

In [7]:

find_cheapest_path("SIN","ZLO")

Cheapest Path from SIN to ZLO: ['SIN', 'NRT', 'LAX', 'ZLO']
Total Price: 1259$
Execution time:  0.00043010711669921875
Memory used: 33248.0 kilobytes

In [8]:

find_cheapest_path("NRT","LHR")

Cheapest Path from NRT to LHR: ['NRT', 'LHR']
Total Price: 580$
Execution time:  2.8133392333984375e-05
Memory used: 108960.0 kilobytes

In [9]:


find_cheapest_path("DEL","ZLO")

Cheapest Path from DEL to ZLO: ['DEL', 'JFK', 'ZLO']
Total Price: 1336$

Execution time:  1.2697097999916878

In [10]:

find_cheapest_path("SIN","ZLO")

Cheapest Path from SIN to ZLO: ['SIN', 'NRT', 'LAX', 'ZLO']
Total Price: 1259$

Execution time:  0.9663789000187535

In [11]:

find_cheapest_path("LHR","ZLO")

Cheapest Path from LHR to ZLO: ['LHR', 'JFK', 'ZLO']
Total Price: 786$

Execution time:  0.9698774999997113

In [12]:

find_cheapest_path("DEL","JFK")

Cheapest Path from DEL to JFK: ['DEL', 'JFK']
Total Price: 998$

Execution time:  0.9693738999776542