📡 Dijkstra’s Algorithm – Comprehensive Study Guide

**Dijkstra’s Algorithm** is a **greedy algorithm** that finds the **shortest path** from a **single source node** to all other nodes in a **graph with non-negative weights**.

⚡ Why is Dijkstra’s Algorithm Important?

• ✅ **Optimized Shortest Path Calculation** – Used in **navigation & GPS routing**.
• ⚡ **Efficient for Graphs with Non-Negative Weights**.
• 📡 **Used in Network Routing Algorithms (OSPF, MPLS)**.
• 🔍 **Applied in AI & Robotics Pathfinding Algorithms**.

📌 Understanding Graph Representation

A graph consists of **vertices (nodes)** and **edges (connections)** with weights. Dijkstra’s algorithm operates on a **weighted graph** where:

• 📌 Each edge has a **non-negative weight**.
• 📌 The algorithm finds the **minimum cost path**.

🛠️ How Dijkstra’s Algorithm Works?

📌 **Step-by-Step Process**

1. ✅ **Initialize** distance of all nodes as **infinity (∞)** except the source node (0).
2. 📌 Insert the source node into a **priority queue (Min-Heap)**.
3. 🔄 Extract the node with the **smallest distance**, update its neighbors.
4. 🔄 Repeat until all nodes have been processed.

🛠️ Dijkstra’s Algorithm Implementation

🔄 **1. Using Priority Queue (Min-Heap) (O(V + E log V))**

                #include 
                using namespace std;
            
                struct Edge {
                    int destination, weight;
                };
            
                void dijkstra(vector> &graph, int source) {
                    int V = graph.size();
                    vector dist(V, INT_MAX);
                    priority_queue, vector>, greater>> pq;
            
                    dist[source] = 0;
                    pq.push({0, source});
            
                    while (!pq.empty()) {
                        int current = pq.top().second;
                        int currentDist = pq.top().first;
                        pq.pop();
            
                        if (currentDist > dist[current]) continue;
            
                        for (Edge edge : graph[current]) {
                            int next = edge.destination;
                            int weight = edge.weight;
                            if (dist[current] + weight < dist[next]) {
                                dist[next] = dist[current] + weight;
                                pq.push({dist[next], next});
                            }
                        }
                    }
            
                    cout << "Shortest Distances from Source: \n";
                    for (int i = 0; i < V; i++) {
                        cout << "Node " << i << " → " << dist[i] << endl;
                    }
                }
            
                int main() {
                    int V = 5;
                    vector> graph(V);
                    graph[0] = {{1, 2}, {2, 4}};
                    graph[1] = {{2, 1}, {3, 7}};
                    graph[2] = {{4, 3}};
                    graph[3] = {{4, 1}};
                    graph[4] = {};
            
                    dijkstra(graph, 0);
                    return 0;
                }
                

⚖️ Dijkstra vs Bellman-Ford vs Floyd-Warshall

⏳ Time Complexity Analysis

• ✅ **Best Case:** O(V + E log V) (Using Min-Heap).
• ⚡ **Worst Case:** O(V²) (Using Simple Array for Priority Queue).

🌍 Real-World Applications of Dijkstra’s Algorithm

• 📡 **Google Maps & GPS Routing** – Shortest path navigation.
• 🔗 **Network Routing (OSPF Protocol)** – Finds the best route between nodes.
• 🛒 **E-commerce Recommendations** – Path optimization in warehouses.
• 🤖 **AI & Robotics** – Pathfinding in self-driving cars.

🔗 Next Topics

• 📌 Bellman-Ford Algorithm
• 🌍 Floyd-Warshall Algorithm
• 📡 Graph Algorithms