SuryaPratapK/Dijkstra algorithm

captSteveRogers · 2020-09-19T11:08:05Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

Venkatraman9214 · 2021-03-07T02:12:27Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

This needs an explanatory video I feel. I don't understand, how the priority queue is defined.

anvudemy · 2021-04-14T10:31:51Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

Good Work @captSteveRogers

pranavbaradkar · 2021-06-24T14:16:15Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

you visiting again and again when the node is already visited. how will you keep track of visited nodes?

ravisha7feb · 2021-07-13T06:10:03Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

you visiting again and again when the node is already visited. how will you keep track of visited nodes?

I think pq.pop() is handling that.

divyanshsaini1805 · 2021-08-24T20:04:23Z

Sir in the video, you promised that you will also provide the code for priority queue, but it seems you forgot. Here is the code. I am glad to contribute. Keep blessing us with your amazing content. This code is non OOP method from gfg and is easy to understand.

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

// function to create an edge
void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    // use priority queue as min heap
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // distance vector
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        // traverse for the neighbors of u
        for(auto x : graph[u]){
            // x = {v, wt}
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

you visiting again and again when the node is already visited. how will you keep track of visited nodes?

We don't, that's why the priority queue implementation used a lot a memory, for a memory efficient solution, use a set, we cant update a set as well but we can remove at any level and insert a new better distance node, whereas in priority queue random access is not possible.

The Code using set is -

void dijkstraSSSP(int src)
{

    unordered_map<int, int> dist;

    for (auto i : m)
    {
        dist[i.first] = INT_MAX;
    }

    //First is distance as set sorts according to first parameter
    set<pair<int, int>> s;

    dist[src] = 0;
    s.insert(make_pair(0, src));

    while (!s.empty())
    {
        auto given_pair = *(s.begin());

        int node = given_pair.second;

        int child_dist = given_pair.first;

        s.erase(given_pair);

        for (auto childPair : m[node])
        {

            if (dist[childPair.first] > child_dist + childPair.second)
            { //dist[node]

                //updation is not possible
                //remove and insert

                int dest = childPair.first;
                auto t = s.find(make_pair(dist[dest], dest));
                if (t != s.end())
                {
                    s.erase(t);
                }

                dist[dest] = child_dist + childPair.second;
                s.insert(make_pair(dist[dest], dest));
            }
        }
    }
    //print
    for (auto distance : dist)
    {
        cout << distance.first << " is located at " << distance.second << endl;
    }
}

Syeed-MD-Talha · 2023-02-11T05:41:03Z

Colorful code, easy to understand ^_^

#include<bits/stdc++.h>
using namespace std;

#define INF 99999

void addEdge(vector<pair<int, int>> graph[], int u, int v, int w){
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void dijkstras(vector<pair<int, int>> graph[], int src, int V){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int>dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    // normal BFS traversal
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        for(auto x : graph[u]){
            int v = x.first;
            int wt = x.second;
            if(dist[v]>dist[u] + wt){
                dist[v] = dist[u] + wt;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout<<"Vertex   Distance from src\n";
    for(int i=0; i<V; i++)
        cout<<i<<"\t"<<dist[i]<<endl;
}

int main(){
    int V = 9;
    vector<pair<int, int>> graph[V];
    addEdge(graph ,0, 1, 4); 
    addEdge(graph ,0, 7, 8); 
    addEdge(graph ,1, 2, 8); 
    addEdge(graph ,1, 7, 11); 
    addEdge(graph ,2, 3, 7); 
    addEdge(graph ,2, 8, 2); 
    addEdge(graph ,2, 5, 4); 
    addEdge(graph ,3, 4, 9); 
    addEdge(graph ,3, 5, 14); 
    addEdge(graph ,4, 5, 10); 
    addEdge(graph ,5, 6, 2); 
    addEdge(graph ,6, 7, 1); 
    addEdge(graph ,6, 8, 6); 
    addEdge(graph ,7, 8, 7); 

    dijkstras(graph, 0, 9);
}

	#include<bits/stdc++.h>
	using namespace std;

	#define V 6 //No of vertices

	int selectMinVertex(vector<int>& value,vector<bool>& processed)
	{
	int minimum = INT_MAX;
	int vertex;
	for(int i=0;i<V;++i)
	{
	if(processed[i]==false && value[i]<minimum)
	{
	vertex = i;
	minimum = value[i];
	}
	}
	return vertex;
	}

	void dijkstra(int graph[V][V])
	{
	int parent[V]; //Stores Shortest Path Structure
	vector<int> value(V,INT_MAX); //Keeps shortest path values to each vertex from source
	vector<bool> processed(V,false); //TRUE->Vertex is processed

	//Assuming start point as Node-0
	parent[0] = -1; //Start node has no parent
	value[0] = 0; //start node has value=0 to get picked 1st

	//Include (V-1) edges to cover all V-vertices
	for(int i=0;i<V-1;++i)
	{
	//Select best Vertex by applying greedy method
	int U = selectMinVertex(value,processed);
	processed[U] = true; //Include new Vertex in shortest Path Graph

	//Relax adjacent vertices (not yet included in shortest path graph)
	for(int j=0;j<V;++j)
	{
	/* 3 conditions to relax:-
	1.Edge is present from U to j.
	2.Vertex j is not included in shortest path graph
	3.Edge weight is smaller than current edge weight
	*/
	if(graph[U][j]!=0 && processed[j]==false && value[U]!=INT_MAX
	&& (value[U]+graph[U][j] < value[j]))
	{
	value[j] = value[U]+graph[U][j];
	parent[j] = U;
	}
	}
	}
	//Print Shortest Path Graph
	for(int i=1;i<V;++i)
	cout<<"U->V: "<<parent[i]<<"->"<<i<<" wt = "<<graph[parent[i]][i]<<"\n";
	}

	int main()
	{
	int graph[V][V] = { {0, 1, 4, 0, 0, 0},
	{1, 0, 4, 2, 7, 0},
	{4, 4, 0, 3, 5, 0},
	{0, 2, 3, 0, 4, 6},
	{0, 7, 5, 4, 0, 7},
	{0, 0, 0, 6, 7, 0} };

	dijkstra(graph);
	return 0;
	}

	//TIME COMPLEXITY: O(V^2)
	//TIME COMPLEXITY: (using Min-Heap + Adjacency_List): O(ElogV)

SuryaPratapK/Dijkstra algorithm

captSteveRogers commented Sep 19, 2020

Venkatraman9214 commented Mar 7, 2021

anvudemy commented Apr 14, 2021

pranavbaradkar commented Jun 24, 2021

ravisha7feb commented Jul 13, 2021

divyanshsaini1805 commented Aug 24, 2021

Syeed-MD-Talha commented Feb 11, 2023