Dijkstra's Algorithm for Adjacency List Representation • T…

Dijkstra's Algorithm for Adjacency List Representation

• The code implements a graph data structure using an adjacency list, where each node includes a destination vertex, weight, and a pointer to the next node.
• A `Graph` structure is defined to store the number of vertices and an array of adjacency lists for each vertex.
• The `newAdjListNode` function allocates memory for a new adjacency list node and initializes its destination vertex and weight.
• The `createGraph` function initializes a graph with a specified number of vertices, setting all adjacency list heads to NULL.
• The `addEdge` function creates an undirected edge between two vertices with a specified weight by adding two adjacency list nodes.
• A min-heap data structure is defined to support Dijkstra's algorithm, including functions for creating the heap, extracting the minimum node, and decreasing a node's key.
• The `minHeapify` function ensures the min-heap property is maintained after node extraction or key decrease operations.
• The `dijkstra` function implements Dijkstra's algorithm to find the shortest paths from a source vertex to all other vertices in the graph.
• The algorithm initializes all vertex distances to infinity, sets the source vertex distance to zero, and uses the min-heap for efficient graph exploration.
• The results of the shortest paths are printed in a formatted manner, displaying each vertex and its distance from the source.
• The `main` function creates a graph with 9 vertices, adds edges with specified weights, and invokes the Dijkstra function starting from vertex 0.