DSA Python Project – City Map Navigation

Program 1

# Project Title: City Map Navigation using Graphs

# Objective:
# To build a simple navigation system that finds the shortest path between a source city 
# and all other cities using Dijkstra's Algorithm — one of the most efficient ways to compute 
# shortest paths in a weighted graph.

# Data Structures Used:

# Graph (Adjacency Matrix):
# Stores the map as a 2D array where each cell adjMatrix[i][j] 
# represents the distance between city i and city j.
# If there is no direct road, the distance is set to a high value (INF).
# Arrays:

# dist[]: To hold the minimum distances from the source city.
# visited[]: To keep track of cities already included in the shortest path tree.
# prev[]: To reconstruct the path (stores the previous city for each destination).

# Project Work Flow:

# 1. City and Road Input:
# The user first inputs how many cities are in the map.
# For each city, a name is provided (e.g., "Indore", "Pune").
# The user then enters how many roads exist and the distance between city pairs using their indices.

# Option 1: Show Adjacency Matrix

# Displays a table of all city-to-city distances.
# Useful for visualizing the city graph.

# Option 2: Find Shortest Paths

# User selects a source city.
# The program uses Dijkstra’s algorithm to calculate the shortest distances from the 
# source to all other cities.
# It also prints the actual path taken from the source to each city.

# Option 3: Exit



import sys

INF = float('inf')

class Graph:
    def __init__(self, vertices):  # 4
        self.vertices = vertices
        self.adj_matrix = [[INF] * vertices for _ in range(vertices)]
        self.city_names = [""] * vertices

    def add_edge(self, src, dest, weight):   # 0 1 300
        self.adj_matrix[src][dest] = weight
        self.adj_matrix[dest][src] = weight  # Undirected

    def set_city_name(self, index, name):
        self.city_names[index] = name

    def display_matrix(self):
        print("\nAdjacency Matrix:")
        print("       ", end="")
        for name in self.city_names:
            print(f"{name:>10}", end="")
        print()
        for i in range(self.vertices):             # row
            print(f"{self.city_names[i]:>10}", end="")
            for j in range(self.vertices):       # col
                if self.adj_matrix[i][j] == INF:
                    print(f"{'∞':>10}", end="")
                else:
                    print(f"{self.adj_matrix[i][j]:>10}", end="")
            print()

    def dijkstra(self, src):  # 0
        dist = [INF] * self.vertices
        visited = [False] * self.vertices
        prev = [-1] * self.vertices
        dist[src] = 0

        for _ in range(self.vertices - 1):
            u = self.min_distance(dist, visited)
            visited[u] = True

            for v in range(self.vertices):
                if not visited[v] and self.adj_matrix[u][v] != INF and dist[u] + self.adj_matrix[u][v] < dist[v]:
                    dist[v] = dist[u] + self.adj_matrix[u][v]
                    prev[v] = u

        print(f"\nShortest paths from {self.city_names[src]}:")
        for i in range(self.vertices):
            if i != src:
                print(f"To {self.city_names[i]} - Distance: {dist[i] if dist[i] != INF else '∞'} - Path: ", end="")
                self.print_path(prev, i)
                print(self.city_names[i])

    def min_distance(self, dist, visited):
        min_val = INF
        min_index = -1
        for i in range(self.vertices):
            if not visited[i] and dist[i] < min_val:
                min_val = dist[i]
                min_index = i
        return min_index

    def print_path(self, prev, j):
        if prev[j] == -1:
            return
        self.print_path(prev, prev[j])
        print(self.city_names[prev[j]] + " -> ", end="")

# -------- Main Program --------

def main():
    n = int(input("Enter number of cities: "))   #n= 4
    g = Graph(n)   # 4

    for i in range(n):
        name = input(f"Enter name of city {i}: ")
        g.set_city_name(i, name)

    e = int(input("Enter number of roads: "))
    for i in range(e):
        print(f"Enter road {i+1} (source_index destination_index distance): ", end="")
        src, dest, dist = map(int, input().split())
        g.add_edge(src, dest, dist)  # 0 1 200

    while True:
        print("\n---------- City Map Navigation Menu -------------")
        print("1. Show Adjacency Matrix")
        print("2. Find Shortest Paths")
        print("3. Exit")
        print("-------------------------------------------------")
        choice = int(input("Enter your choice: "))

        if choice == 1:
            g.display_matrix()
        elif choice == 2:
            src = int(input("Enter source city index: "))  # 0
            g.dijkstra(src)  # 0
        elif choice == 3:
            print("Exiting...")
            break
        else:
            print("Invalid choice. Try again.")

if __name__ == "__main__":
    main()