C++ | Dijkstra's Shortest Path Algorithm Explained | 99.61% Faster
Firstly, from the given input vector, we have to make the adjacency list for the required directed weighted graph. \n\nA corner condition: If node k has no outg
Firstly, from the given input vector, we have to make the adjacency list for the required **directed weighted graph**. \n\nA corner condition: If node k has no outgoing connections, then it is impossible for signal to reach to all nodes, we return -1 in this case.\n\n### Approach : Dijkstra\'s Shortest Path Algorithm (99.61% faster)\n\nHere, our priority is to reach to all nodes anyhow. So, we calculate the minimum distance to all other nodes from given "k" node. For getting minimum distance every time, we make a minimum heap using C++ STL priority queue. \n\nOnce we have visited all feasible nodes from given "k" node, we have the minimum distances of the nodes which we have visited from "k". So now, our answer would be the maximum distance in these all distances. \n\nIf our maximum distance is INT_MAX, that means we have not visited some nodes (hence distance vector was initialized with INT_MAX in starting). So we will return -1.\nElse we will return maximum distance.\n\nMy Submission:\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        vector<pair<int , int>> adj[n + 1];         // Graph Container (Adjacency List)\n   \n        for(int i = 0 ; i < times.size() ; ++i){\n            adj[times[i][0]].push_back(make_pair(times[i][1] , times[i][2]));   //Constructing the graph.\n        }\n        \n        vector<bool> visited(n + 1 , false);        // Visited Array\n        vector<int> distances(n + 1 , INT_MAX);     // Minimum Distance of each node from k, initialized by INT_MAX.\n        if(adj[k].size() == 0){                     // If there is no outgoing edge from k, return -1.\n            return -1;\n        } else {                                // Standard Dijkstra Algorithm Implementation\n            priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> dijkstra_queue;\n            distances[k] = 0;\n            int count = 0;\n            dijkstra_queue.push(make_pair(0 , k));\n            while(count < n && !dijkstra_queue.empty()){\n                int distance = dijkstra_queue.top().first;\n                int node = dijkstra_queue.top().second;\n                dijkstra_queue.pop();\n                if(visited[node]){\n                    continue;\n                }\n                visited[node] = true;\n                distances[node] = distance;\n                count++;\n                for(auto it : adj[node]){\n                    int next_node = it.first;\n                    int next_distance = it.second;\n                    if(!visited[next_node]){\n                        dijkstra_queue.push(make_pair(distance + next_distance , next_node));\n                    }\n                }\n            }\n        }\n        int answer = 0;\n        for(int i = 1 ; i < distances.size() ; ++i){    \n            answer = max(answer , distances[i]);    // Distance of farthest node would be our answer.\n        }\n        if(answer == INT_MAX){      // Means we have missed some node.\n            return -1;\n        }\n        return answer;              \n    }\n};\n```\n**PLEASE UPVOTE IT IF YOU LIKED IT, IT REALLY MOTIVATES :)**
['C', 'C++']