maths el.py

import heapq

class Graph:
    def __init__(self, num_vertices):
        self.graph = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))  # (neighbor, weight)

    def dijkstra(self, src, is_disaster=None):
        dist = [float('inf')] * len(self.graph)
        dist[src] = 0
        prev = [-1] * len(self.graph)

        pq = [(0, src)]  # (distance, vertex)
        heapq.heapify(pq)

        while pq:
            u = heapq.heappop(pq)[1]

            # Disaster handling: if a disaster occurs at u, make it unreachable
            if is_disaster and is_disaster(u):
                continue

            for v, weight in self.graph[u]:
                alt = dist[u] + weight
                if dist[v] > alt:
                    dist[v] = alt
                    prev[v] = u
                    heapq.heappush(pq, (alt, v))

        return dist, prev

# Example usage
locations = ["Kr Pura", "Halasuru", "Kr Market", "VV Pura", "Majestic"]
num_vertices = len(locations)
graph = Graph(num_vertices)

# Add edges (roads/paths) and weights (distances)
graph.add_edge(0, 1, 5)  # Kr Pura -> Halasuru (5 km)
graph.add_edge(0, 2, 8)  # Kr Pura -> Kr Market (8 km)
graph.add_edge(1, 2, 2)  # Halasuru -> Kr Market (2 km)
graph.add_edge(1, 3, 4)  # Halasuru -> VV Pura (4 km)
graph.add_edge(2, 4, 3)  # Kr Market -> Majestic (3 km)
graph.add_edge(3, 4, 1)  # VV Pura -> Majestic (1 km)

# Function to simulate a disaster (replace with actual logic)
def is_disaster(location):
    if location == "Kr Market":  # Simulate disaster at Kr Market
        return True
    return False

# Find shortest path from Kr Pura (source) to all other locations
source = locations.index("Kr Pura")
dist, prev = graph.dijkstra(source, is_disaster)

# Print shortest distances
for i, location in enumerate(locations):
    if dist[i] == float('inf'):
        print(f"Shortest path to {location} not found (possibly due to disaster)")
    else:
        print(f"Shortest path to {location}: {dist[i]} km")

# Optionally, reconstruct the shortest path using the predecessor array (prev)