Ch-Assignment4-Djikstra

import heapq

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
        # It initializes the graph with the given number of vertices and an empty adjacency list.
        for _ in range(vertices):
            self.graph.append([])

    # This method allows you to add an edge between vertices u and v with a weight w to the graph's adjacency list
    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def dijkstra(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0
        pq = [(0, src)]

        # Pop the vertex with the minimum distance from the priority queue.
        # This ensures that the vertex with the shortest tentative distance is processed first. distance stores the distance, and u stores the vertex.
        while pq:
            distance, u = heapq.heappop(pq)

            # If the extracted distance is greater than the stored distance for vertex u in the dist array,
            # skip this vertex and continue to the next one.
            if distance > dist[u]:
                continue
            for v, weight in self.graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(pq, (dist[v], v))
        return dist

# Input-driven code
if __name__ == "__main__":
    num_vertices = int(input("Enter the number of vertices: "))
    g = Graph(num_vertices)

    num_edges = int(input("Enter the number of edges: "))
    for _ in range(num_edges):
        u, v, w = map(int, input("Enter source, destination, and weight separated by spaces: ").split())
        g.add_edge(u, v, w)

    start_node = int(input("Enter the source node: "))
    shortest_distances = g.dijkstra(start_node)

    print("Vertex \t Distance from Source")
    for i in range(num_vertices):
        print(i, "\t\t", shortest_distances[i])