Dijkstra’s shortest path algorithm
Relaxation Rule :
dist[v] = min( dist[v], (dist[u] + cost[u,v] )
Approach :
1) Initialize distances of all vertices as infinite.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
distance) is used used as first item of pair
as first item is by default used to compare
two pairs
3) Insert source vertex into pq and make its
distance as 0.
4) While pq doesn't become empty
a) Extract minimum distance vertex from pq.
Let the extracted vertex be u.
b) Loop through all adjacent of u and do
following for every vertex v.
// If there is a shorter path to v
// through u.
If dist[u] + weight(u, v)< dist[v]
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is
already there)
5) Print distance array dist[] to print all shortest
paths.Whenever distance of a vertex is reduced, we add one more instance of vertex in priority_queue. Even if there are multiple instances, we only consider the instance with minimum distance and ignore other instances since minHeap stores the min at the top
The time complexity remains O(ELogV)) as there will be at most O(E) vertices in priority queue and O(Log E) is same as O(Log V)
Code ( O(NlogN) time & O(N) space ) :
#include<bits/stdc++.h>
using namespace std;int main(){
int n,m,source;
cin >> n >> m;
vector<pair<int,int> > adj[n+1];
// 1-indexed adjacency list for of graph that's why n+1int a,b,wt;
for(int i = 0; i<m ; i++){
cin >> a >> b >> wt;
g[a].push_back(make_pair(b,wt));
g[b].push_back(make_pair(a,wt));
}
cin >> source;
// Dijkstra's algorithm begins from here
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > pq; // min-heap
vector<int> dist(n+1,INT_MAX);
dist[source] = 0;
pq.push(make_pair(0,source)); // (dist,vertex)
// here distance will be the key for min heap so shorter
// distwill always be at top
while(!pq.empty())
{
int currDist=pq.top().first;
int currNode=pq.top().second;
pq.pop();
for(auto it: adj[currNode])
{
int nextNode=it->first;
int edge=it->second; // this is the weighted edge
if(dist[nextNode] < dist[currNode]+edge)
{
dist[nextNode]=dist[currNode]+edge;
pq.push({dist[nextNode],nextNode});
}
}
}
cout << "The distances from source, " << source << ", are : \n";
for(int i = 1 ; i<=n ; i++) cout << distTo[i] << " ";
cout << "\n";
return 0;
}
Notes:
1) The code calculates shortest distance, but doesn’t calculate the path information. We can create a parent array, update the parent array when distance is updated and use it show the shortest path from source to different vertices.
2) The code is for undirected graph, same dijkstra function can be used for directed graphs also.
3) The code finds shortest distances from source to all vertices. If we are interested only in shortest distance from the source to a single target, we can break the for the loop when the picked minimum distance vertex is equal to target (Step 3.a of the algorithm).
4) Time Complexity of the implementation is O(V²) if matrix is used & If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap. (which I did xD )
5) Dijkstra’s algorithm doesn’t work for graphs with negative weight cycles, it may give correct results for a graph with negative edges. For graphs with negative weight edges and cycles, Bellman–Ford algorithm can be used, we will soon be discussing it as a separate post.
See here & try to apply Dijkstra ‘s algo here…we already visited node 2 with dist as 3 but due to negtative weights , now the new dist of node 2 is -3 which should be the ans but since we already visited the node we cannot again visit the nodes due to dijkstra
Spanning Tree
Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees.
If a graph is a complete graph with n vertices, then total number of spanning trees is n^(n-2)
Min Spanning Tree (MST)
- A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a spanning tree with a weight less than or equal to the weight of every other spanning tree.
- The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.
How many edges does a minimum spanning tree has?
A minimum spanning tree has (V — 1) edges where V is the number of vertices in the given graph.
Note: For non connected graph we cannot form spanning trees
Prim’s Algo for Min Spanning Tree (MST)| Greedy
We start from any one vertex and keep adding edges with the lowest weight until we reach our goal.
The steps for implementing Prim’s algorithm are as follows:
- Initialize the minimum spanning tree with any vertex (usually the 1st)
- Find all the adjacent edges to the selected vertex and select the edge with the min weight (incase of multiple same min, select any one)
- Keep repeating step 2 until we get a minimum spanning tree
- Make sure while selecting the min edge that it always connects a new vertex else a cycle will be formed which we dont want(so in a way we select the next min)
Approach for C++ implementation
3 arrays : key[ ] for choosing the next vertex with min weight, mstSet[ ] for to to represent the vertices present in MST, parent[ ] for printing the MST
Initially choose min value vertex i.e. zero and update its key as zero so that it is chosen first and now take a loop for V-1 times and in each iteration we’ll get a vertex which will be min value in the key [ ] , mark is as included in MST and then we consider its adjacent vertices & update their parent & key only with its weight and would not mark them as included because that we would do in next iteration for them i.e in each iteration we only mark 1 vertex with the min key and for its adjacent vertives we just update their parent with that marked vertex & key with their weight of the edge
Code (using matrix)
#include<bits/stdc++.h>
using namespace std;int main(){
int N,m;
cin >> N >> m;
vector<pair<int,int> > adj[N];int a,b,wt;
for(int i = 0; i<m ; i++){
cin >> a >> b >> wt;
adj[a].push_back(make_pair(b,wt));
adj[b].push_back(make_pair(a,wt));
}
int parent[N]; // to store constructed MST
int key[N]; // to decide the min weight edge to select the // next vertex
bool mstSet[N]; // to check for visited/unvisited nodes &
// To represent set of vertices included in MST
for (int i = 0; i < N; i++)
key[i] = INT_MAX, mstSet[i] = false; key[0] = 0; // Make key 0 so that this vertex is picked 1st
parent[0] = -1; //1st node is root of the MST it has no parent for (int count = 0; count < N - 1; count++) // Edges=vertex-1
{
// Pick the minimum key vertex from the
// set of vertices not yet included in MST int mini = INT_MAX, u;
for (int v = 0; v < N; v++)
if (mstSet[v] == false && key[v] < mini)
mini = key[v], u = v; // Add the picked vertex to the MST Set
mstSet[u] = true; // Update key value and parent index of
// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (auto it : adj[u]) {
int v = it.first;
int weight = it.second;
if (mstSet[v] == false && weight < key[v])
parent[v] = u, key[v] = weight;
}
}
for (int i = 1; i < N; i++)
cout << parent[i] << " - " << i <<" \n";
return 0;
}
Time Complexity of the above program is O(V²).
Note: The following code snippet has time complexity of O(N+E) not O(N²)
for (int count = 0; count < N - 1; count++)
{
for (auto it : adj[u]) {
int v = it.first;
int weight = it.second;
if (mstSet[v] == false && weight < key[v])
parent[v] = u, key[v] = weight;
}
}So the above code has time comp = 0(V+E)*N=O(V²)
Optimal Approach
Instead of traversing the whole key[ ] to find the min we can use min heap so that O(N) becomes O(logN)
1) Initialize keys of all vertices as infinite and
parent of every vertex as -1.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
key) is used used as first item of pair
as first item is by default used to compare
two pairs.
3) Initialize all vertices as not part of MST yet.
We use boolean array inMST[] for this purpose.
This array is required to make sure that an already
considered vertex is not included in pq again. We require this array here
because key value of a processed vertex may decrease
if not checked.
4) Insert source vertex into pq and make its key as 0.
5) While either pq doesn't become empty
a) Extract minimum key vertex from pq.
Let the extracted vertex be u.
b) Include u in MST using inMST[u] = true.
c) Loop through all adjacent of u and do
following for every vertex v.
// If weight of edge (u,v) is smaller than
// key of v and v is not already in MST
If inMST[v] = false && key[v] > weight(u, v)
(i) Update key of v, i.e., do
key[v] = weight(u, v)
(ii) Insert v into the pq
(iv) parent[v] = u
6) Print MST edges using parent array.Code :
#include<bits/stdc++.h>
using namespace std;int main(){
int N,m;
cin >> N >> m;
vector<pair<int,int> > adj[N];int a,b,wt;
for(int i = 0; i<m ; i++){
cin >> a >> b >> wt;
adj[a].push_back(make_pair(b,wt));
adj[b].push_back(make_pair(a,wt));
}
int parent[N];
int key[N];
bool mstSet[N];
for (int i = 0; i < N; i++)
key[i] = INT_MAX, mstSet[i] = false;
priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq;key[0] = 0;
parent[0] = -1;
pq.push({0, 0});
while(!pq.empty())
{
int u = pq.top().second;
pq.pop();
mstSet[u] = true;
for (auto it : adj[u]) {
int v = it.first;
int weight = it.second;
if (mstSet[v] == false && weight < key[v]) {
parent[v] = u;
key[v] = weight;
pq.push({key[v], v});
}
}
}
for (int i = 1; i < N; i++)
cout << parent[i] << " - " << i <<" \n";
return 0;
}
Time Complexity Analysis
- If adjacency list is used to represent the graph, then using breadth first search, all the vertices can be traversed in O(V + E) time.
- We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included in the MST.
- To get the minimum weight edge, we use min heap as a priority queue.
- Min heap operations like extracting minimum element takes O(logV) time.
So, overall time complexity
= O(E + V) x O(logV)
= O((E + V)logV)
= O(ElogV)
How Printing takes place ?
Suppose that’s how a MST was formed step by step then printing will be as follow : (see the pic)
Question: The task is to find the sum of weights of the edges of the Minimum Spanning Tree.(here check my solution) or hackerearth sexy solution
Disjoint Set
Must see resources :
GFG Disjoint Set , DSU detect cycle set 1, DSU detect cycle set 2
int parent[1000];
int rank[10000];void make_set()
{
for(int i=0;i<n;i++) {
parent[i]=i;
rank[i]=0;
}
}// NAIVE
int findParent(int node)
{
if(parent[node]==node)
return node;
else return findParent(parent[node]);
}
// COMPRESSED (this will update the parent each time)
int findParent(int node)
{
if(parent[node]==node)
return node;
else return parent[node] = findParent(parent[node]);
}
void union(int u, int v)
{
u=findParent(u);
v=findParent(v);
if(rank[u]<rank[v])
parent[u]=v;
else if(rank[u]>rank[v])
parent[v]=u;
else
{
parent[u]=v; // or parent[v]=u DO ANY ONE
rank[v]++; // or rank[u]++;
}
}
void main()
{
make_set();
}
Now we are ready to do Kruskal’s Algo
Approach:
We start from the edges with the lowest weight and keep adding edges until we reach our goal.
The steps for implementing Kruskal’s algorithm are as follows:
- Sort all the edges from low weight to high
- Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
- Keep adding edges until we reach all vertices.
Note: we dont take any adjacent list here because we need to store edges only (not to traverse the graph ) and to sort edges in ascending order according to their weights so use a structure instead
We’ll take vector<pair<int,int>> mst to store the edges of the MST
To detect a cycle , we’ll find parent of the 2 components if they are same then a cycle exists
Code : ( O(E logV time ) )
#include<bits/stdc++.h>
using namespace std;
struct node {
int u;
int v;
int wt;
node(int first, int second, int weight) {
u = first;
v = second;
wt = weight;
}
};bool comp(node a, node b) {
return a.wt < b.wt;
}int findParent(int u, vector<int> &parent) {
if(u == parent[u]) return u;
return parent[u] = findParent(parent[u], parent);
}void unionn(int u, int v, vector<int> &parent, vector<int> &rank) {
u = findParent(u, parent);
v = findParent(v, parent);
if(rank[u] < rank[v]) {
parent[u] = v;
}
else if(rank[v] < rank[u]) {
parent[v] = u;
}
else {
parent[v] = u;
rank[u]++;
}
}
int main(){
int N,m;
cin >> N >> m;
vector<node> edges;
for(int i = 0;i<m;i++) {
int u, v, wt;
cin >> u >> v >> wt;
edges.push_back(node(u, v, wt));
}
sort(edges.begin(), edges.end(), comp);
vector<int> parent(N);
for(int i = 0;i<N;i++)
parent[i] = i;
vector<int> rank(N, 0);
int cost = 0;
vector<pair<int,int>> mst;
for(auto it : edges) {
if(findParent(it.v, parent) != findParent(it.u, parent)) {
cost += it.wt;
mst.push_back({it.u, it.v});
unionn(it.u, it.v, parent, rank);
}
}
cout << cost << endl;
for(auto it : mst) cout << it.first << " - " << it.second << endl;
return 0;
}
Another implementation (hackerearth)
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];
void initialize()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
// Selecting edges one by one in increasing order from the beginning
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
// Check if the selected edge is creating a cycle or not
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
initialize();
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
// Sort the edges in the ascending order
sort(p, p + edges);
minimumCost = kruskal(p);
cout << minimumCost << endl;
return 0;
}