Dijkstra algorithm

#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)

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;
    }
}

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);
}