Dijkstra's Algo : You need to find the shortest distance from the source to all the other nodes in the graph. It can be done over directed or undirected graph. First you need to maintain a pq Or set or multiset, then you need to perform bfs over every child of the visited node and update the current distance to the minimum possible one or make no changes. Then simply do this for all the nodes, untill all the nodes are marked visited. At the end we have the shortest distance, from source to all the other nodes in the graph.
@@kangsoo5222 bfs can also find shortest path because of level wise traversal but the only diff is Dijkstra can find with the weighted graph while for bfs it should be equally weighted
#include using namespace std; const int inf = 1e7; int main() { int nodes, edges; cin >> nodes >> edges; // Initialize the graph as an adjacency list vector graph(nodes + 1);
// Initialize distance array with infinity vector dist(nodes + 1, inf); // Read edges and weights for (int i = 0; i < edges; ++i) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } int source; cin >> source; dist[source] = 0; // Using a set to keep track of vertices with their current distance set st; // {weight, vertex} st.insert({0, source}); // Dijkstra's algorithm while (!st.empty()) { auto node = *st.begin(); int v = node.second; int v_dist = node.first; st.erase(st.begin()); // Traverse through all neighbors of vertex v for (auto child : graph[v]) { int child_v = child.first; int w = child.second; // Relaxation step if (dist[v] + w < dist[child_v]) { dist[child_v] = dist[v] + w; st.insert({dist[child_v], child_v}); } } } // Output distances from source to all nodes for (int i = 1; i
If someones is intersted in knowing the dist array check that LUV mentioned at 24:23, Here it is: //if edges from this node has already //been relaxed; avoid work if(dist[u] < d) continue; The idea is simple, the duplicate entri's 'd' (distance from source) will be more than optimal value of dist[u].
Best Explanation on Every topics. Pls also continue with the LeetCode practice. I think you should also add Leetcode daily challenge which happens in the leetcode. Your explanation will be very helpful for everyone. Thanks a lot.
#include using namespace std; const int inf = 1e7; int main() { int nodes, edges; cin >> nodes >> edges; // Initialize the graph as an adjacency list vector graph(nodes + 1);
// Initialize distance array with infinity vector dist(nodes + 1, inf); // Read edges and weights for (int i = 0; i < edges; ++i) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } int source; cin >> source; dist[source] = 0; // Using a set to keep track of vertices with their current distance set st; // {weight, vertex} st.insert({0, source}); // Dijkstra's algorithm while (!st.empty()) { auto node = *st.begin(); int v = node.second; int v_dist = node.first; st.erase(st.begin()); // Traverse through all neighbors of vertex v for (auto child : graph[v]) { int child_v = child.first; int w = child.second; // Relaxation step if (dist[v] + w < dist[child_v]) { dist[child_v] = dist[v] + w; st.insert({dist[child_v], child_v}); } } } // Output distances from source to all nodes for (int i = 1; i
```If you are having trouble in leetcode to declare N and INF, write like this``` class Solution { public: constexpr static int N = 1e4; constexpr static int INF = 1e7 + 123; int dijkstra(int source, int nodes, vector< pair > graph[N] ) { } int networkDelayTime(vector& times, int n, int k) { vector graph[N];// {node,weight} for (auto vec : times) { // times is a vector of vector, inside vector size is 3 graph[vec[0]].push_back({vec[1], vec[2]}); } int ans = dijkstra(k, n, graph); return ans; }
NOTE--- Why we use visited array when we get answer without that also because we don't insert a vertex into set until and unless we got less distance from current distance.
Because as explained in the example at the beginning, a node could be inserted twice with different distances. So we do not want to process it again the 2nd time.
Hello thanks for the video i think i used similar logic to implement the above in java i had a question for you what if someone says if we have to apply heuristic to this and convert it into a* algorithm then(for now i can only think of ranking nodes on the basis of their children) and the giving priority to those nodes having more children! What's your thoughts about this
why are we using PQ ? we can simply do BFS also . vector dijkstra(int V, vector adj[], int S) { vector dist(V,INT_MAX); dist[S]=0; queue q; q.push(S); while(!q.empty()){ int node=q.front(); q.pop(); for(auto i:adj[node]) { if(dist[node]+i[1]
#include using namespace std; // N represent the maxm nodes the graph can have // INF represent the infinity const int N = 1e5 + 10; const int INF = 1e9 + 10; // pair--> node, weight vector g[N]; void dijkstra(int source, vector& dist) { vector vis(N, 0); // pair--> weight, node // weight first hai q ki sorting automatic on first set st; st.insert({0, source}); dist[source] = 0; while (!st.empty()) { // getting the smallest value from the set \|/ auto node = *st.begin(); int distance = node.first; int v = node.second; //jo item list se nikaal rahe hain usko erase v krna hai set se st.erase(st.begin()); // agr node already visited hai to skip if (vis[v] == 1) continue; vis[v] = 1; // children node pe jayenge // child represents an element of the g[v] container, which likely // represents the adjacency list or set of child nodes for the vertex v in a graph. for (auto child : g[v]) { // graph me ( first -> node ) & ( second-> weight ) int child_v = child.first; int wt = child.second; if (distance + wt < dist[child_v]) { st.erase({dist[child_v], child_v}); // Remove the old entry if present dist[child_v] = distance + wt; st.insert({dist[child_v], child_v}); } } } } int main() { int n = 5; // Number of nodes in the graph int source = 1; vector dist(n + 1, INF); // Initialize dist vector with INF // Add edges to the graph g[1].push_back({2, 10}); g[2].push_back({1, 10}); g[1].push_back({4, 5}); g[4].push_back({1, 5}); g[2].push_back({3, 7}); g[3].push_back({2, 7}); g[3].push_back({4, 2}); g[4].push_back({3, 2}); g[4].push_back({5, 1}); g[5].push_back({4, 1}); dijkstra(source, dist); // Print the shortest distances from the source to all other nodes for (int i = 1; i
In Dijkstra's algorIn Dijkstra's algorithm, we didn't need this visited array as distances always increase. ie; the node which is taken out from priority Queue (visited) is been reached by the shortest possible path. And once taken out from priority queue, node attains its final key value.
@@samagrapathak3854 thanks bro but tum bta skte ho kya aur kya kya topics bache hain Dp k alawa aur course kb tk end hojayega😊😊kyunki mere winter breaks aane wale hain to mai shuru krdoonga Cp
@@harry-cf4ii bhai cp koi course nahi hoti jisko khatam kara ja sake cp is a sport isme parctice kar karke skill develop karni padthi he or practice se aage badte he isme itne topics bhot he beginner ke liye or thoda or karna he to dp me khud specialist tak poch gaya hu
@@samagrapathak3854 kya mai love babbar bhaiya ka C++ DSA Course dekhke pura practise krke khatm krne k baad inn luv bhaiya k CP wale playlist ko shuru karu??ya fir directly idhar se hi shuru karu??am in 1st sem and dont know c of coding right now pls guide me bro😊😊😊
Dijkstra's Algo :
You need to find the shortest distance from the source to all the other nodes in the graph. It can be done over directed or undirected graph.
First you need to maintain a pq Or set or multiset, then you need to perform bfs over every child of the visited node and update the current distance to the minimum possible one or make no changes. Then simply do this for all the nodes, untill all the nodes are marked visited.
At the end we have the shortest distance, from source to all the other nodes in the graph.
added in notes 🙂
what is bfs, pq
@@kangsoo5222 bfs can also find shortest path because of level wise traversal but the only diff is Dijkstra can find with the weighted graph while for bfs it should be equally weighted
#include
using namespace std;
const int inf = 1e7;
int main() {
int nodes, edges;
cin >> nodes >> edges;
// Initialize the graph as an adjacency list
vector graph(nodes + 1);
// Initialize distance array with infinity
vector dist(nodes + 1, inf);
// Read edges and weights
for (int i = 0; i < edges; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
int source;
cin >> source;
dist[source] = 0;
// Using a set to keep track of vertices with their current distance
set st; // {weight, vertex}
st.insert({0, source});
// Dijkstra's algorithm
while (!st.empty()) {
auto node = *st.begin();
int v = node.second;
int v_dist = node.first;
st.erase(st.begin());
// Traverse through all neighbors of vertex v
for (auto child : graph[v]) {
int child_v = child.first;
int w = child.second;
// Relaxation step
if (dist[v] + w < dist[child_v]) {
dist[child_v] = dist[v] + w;
st.insert({dist[child_v], child_v});
}
}
}
// Output distances from source to all nodes
for (int i = 1; i
If someones is intersted in knowing the dist array check that LUV mentioned at 24:23, Here it is:
//if edges from this node has already
//been relaxed; avoid work
if(dist[u] < d)
continue;
The idea is simple, the duplicate entri's 'd' (distance from source) will be more than optimal value of dist[u].
we can also write this check as : if (dist[u] != d)
Best Explanation on Every topics. Pls also continue with the LeetCode practice. I think you should also add Leetcode daily challenge which happens in the leetcode. Your explanation will be very helpful for everyone. Thanks a lot.
Best teacher . Please continue with your work.
There is no need for a visited array because once the distance to a node is least, it will never be added again in the priority queue.
Right but keeping vis array makes sol optimised as you will not process for nodes which you know has got min distance
its need cuz sometimes it might give you TLE, node will not be pushed, but the inner for loop will run to check all its neighbors
My exam is tomorrow and today I am blessed that your video is recommended :)
great boss..
Love from Bangladesh 🇧🇩
Long awaited video
💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛Sexy video.
#include
using namespace std;
const int inf = 1e7;
int main() {
int nodes, edges;
cin >> nodes >> edges;
// Initialize the graph as an adjacency list
vector graph(nodes + 1);
// Initialize distance array with infinity
vector dist(nodes + 1, inf);
// Read edges and weights
for (int i = 0; i < edges; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
int source;
cin >> source;
dist[source] = 0;
// Using a set to keep track of vertices with their current distance
set st; // {weight, vertex}
st.insert({0, source});
// Dijkstra's algorithm
while (!st.empty()) {
auto node = *st.begin();
int v = node.second;
int v_dist = node.first;
st.erase(st.begin());
// Traverse through all neighbors of vertex v
for (auto child : graph[v]) {
int child_v = child.first;
int w = child.second;
// Relaxation step
if (dist[v] + w < dist[child_v]) {
dist[child_v] = dist[v] + w;
st.insert({dist[child_v], child_v});
}
}
}
// Output distances from source to all nodes
for (int i = 1; i
Was waiting for this.... Thankyou SIr!
Bestestt explaination everrr
Back in action 🔥🔥
Luv you luv bhaiya 💗
```If you are having trouble in leetcode to declare N and INF, write like this```
class Solution {
public:
constexpr static int N = 1e4;
constexpr static int INF = 1e7 + 123;
int dijkstra(int source, int nodes, vector< pair > graph[N] ) {
}
int networkDelayTime(vector& times, int n, int k) {
vector graph[N];// {node,weight}
for (auto vec : times) {
// times is a vector of vector, inside vector size is 3
graph[vec[0]].push_back({vec[1], vec[2]});
}
int ans = dijkstra(k, n, graph);
return ans;
}
💛 Awesome explanation 👍🙏
Why do we need a set when we already have the dist[ ]?
PLease solve more leetcode questions, If possible take live problem solving session!!
👏👏amazing content!
💛 awesome 🎉
Love you bhaiya love you💛💛💛💛💛💛
fabulous work for Dijkstra and Floyd Warshall. pls explain Bellman-Ford
Behtareen
Mast explanation
Hope our family reaches to 100k before next video.
Best 🔥
Welcome back 🔥
NOTE--- Why we use visited array when we get answer without that also because we don't insert a vertex into set until and unless we got less distance from current distance.
Because as explained in the example at the beginning, a node could be inserted twice with different distances. So we do not want to process it again the 2nd time.
@@rdias002bcause it helps not visit the node again if it is a non directed graph....
24:54 the algorithm would run for a infinite time, because you are not removing the node from the set. anyways, thanks for your efforts
thanks alot big brother
Nice video! Love you babbar.
abey saale dono alag hai
We miss you Luv ❤
Bhaiyya 500 Leetcode questions ho gaye bas 1000 bache h Elon Musk se aage jane ke liye 🙂🌝
Thank you sir your video very helpfull😇
Thanks for this amazing explanation
bhaiya iske baad dynamic programming pdha dena plzz
AWmsm ❤❤
Hello thanks for the video i think i used similar logic to implement the above in java i had a question for you what if someone says if we have to apply heuristic to this and convert it into a* algorithm then(for now i can only think of ranking nodes on the basis of their children) and the giving priority to those nodes having more children! What's your thoughts about this
one doubt , why are we popping just minimum distance node (node at top) from *set* ??
Note taking app konsa hai bhaiya ?
Bhai linked list me bahot problem hoti ... Is pr bhi video Banao bhai please
annoing background music !
Thank you sir
❤Thank You❤
I love the music
You are *legend*
Bhaiya jaldi jaldi videos dal diya karo!!
I don't know why I have this doubt, but can't we use map instead of set ?
u can
why are we using PQ ? we can simply do BFS also .
vector dijkstra(int V, vector adj[], int S)
{
vector dist(V,INT_MAX);
dist[S]=0;
queue q;
q.push(S);
while(!q.empty()){
int node=q.front();
q.pop();
for(auto i:adj[node])
{
if(dist[node]+i[1]
as per the logic of the algo we need to visit min weighted neighbour first,that is why we require priority queue
@@mallakbasheersyed1859 thenks
How to store the shortest path of every source to node?
Please explain bellman Ford i know the algorithm but struggling to find logic behind that 😢
great
Is there any use of visited array? The code works fine without it too.
you can save some iteration nothing else
u will get tle for larger input
💛captain
thanks bro
I think in worst case, the set size can become order of V^2, not V as said by striver🤔🤔
class Solution {
public:
const int N = 1e5+10;
const int INF = 1e9+10;
int djikstra(int source ,int n, vector g){
vector vis(N,0);
vector dist(N,INF);
set st;
st.insert({0,source});
dist[source] = 0;
while(st.size() > 0){
auto node = *st.begin();
int v = node.second;
int v_dist = node.first;
st.erase(st.begin());
if(vis[v]) continue;
vis[v] = 1;
for(auto child : g[v]){
int child_v = child.first;
int wt = child.second;
if(dist[v] + wt < dist[child_v]){
dist[child_v] = dist[v] + wt;
st.insert({dist[child_v], child_v});
}
}
}
int ans = 0;
for(int i = 1; i decltype(__cont.begin())
^ ~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/range_access.h:58:5: note: candidate template ignored: substitution failure [with _Container = std::pair]: no member named 'begin' in 'std::pair'
begin(const _Container& __cont) -
bestt!!!!
Is CP book Competitive Programming 4 by Steven Halim any help?
Yes it is good to start. You can use.
💛💛💛💛💛💛💛
dijkstra💛
#include
using namespace std;
// N represent the maxm nodes the graph can have
// INF represent the infinity
const int N = 1e5 + 10;
const int INF = 1e9 + 10;
// pair--> node, weight
vector g[N];
void dijkstra(int source, vector& dist)
{
vector vis(N, 0);
// pair--> weight, node
// weight first hai q ki sorting automatic on first
set st;
st.insert({0, source});
dist[source] = 0;
while (!st.empty())
{
// getting the smallest value from the set \|/
auto node = *st.begin();
int distance = node.first;
int v = node.second;
//jo item list se nikaal rahe hain usko erase v krna hai set se
st.erase(st.begin());
// agr node already visited hai to skip
if (vis[v] == 1)
continue;
vis[v] = 1;
// children node pe jayenge
// child represents an element of the g[v] container, which likely
// represents the adjacency list or set of child nodes for the vertex v in a graph.
for (auto child : g[v])
{
// graph me ( first -> node ) & ( second-> weight )
int child_v = child.first;
int wt = child.second;
if (distance + wt < dist[child_v])
{
st.erase({dist[child_v], child_v}); // Remove the old entry if present
dist[child_v] = distance + wt;
st.insert({dist[child_v], child_v});
}
}
}
}
int main()
{
int n = 5; // Number of nodes in the graph
int source = 1;
vector dist(n + 1, INF); // Initialize dist vector with INF
// Add edges to the graph
g[1].push_back({2, 10});
g[2].push_back({1, 10});
g[1].push_back({4, 5});
g[4].push_back({1, 5});
g[2].push_back({3, 7});
g[3].push_back({2, 7});
g[3].push_back({4, 2});
g[4].push_back({3, 2});
g[4].push_back({5, 1});
g[5].push_back({4, 1});
dijkstra(source, dist);
// Print the shortest distances from the source to all other nodes
for (int i = 1; i
💛💛💛💛💛💛💛💛💛💛💛💛💛
😊
💛 => I have a suggestion, along with advanced graph algorithm video share 5 medium-hard quality problems links to practice.
🔥
💛 💛
💛
In Dijkstra's algorIn Dijkstra's algorithm, we didn't need this visited array as
distances always increase.
ie; the node which is taken out from priority Queue (visited) is been reached by the shortest possible path.
And once taken out from priority queue, node attains its final key value.
Opp
💛💛💛💛
♥️
🤗🤗
11-aug 2022
♥
Greedy approach se hi hai na ?
bro PLEASE turn on english subtitles for your videos PLEASE
Bhaiya CP ka course kb tk khatam hojayega kya ap ek expected month bata skte hain??i mean 2022 mai konse month tk pura complete hojayega
Bhai jitna luv sir ne padhya he abhi tak utne se hi codeforces pe expert ban sakte ho bus dp or ati ho to
@@samagrapathak3854 thanks bro but tum bta skte ho kya aur kya kya topics bache hain Dp k alawa aur course kb tk end hojayega😊😊kyunki mere winter breaks aane wale hain to mai shuru krdoonga Cp
@@harry-cf4ii bhai cp koi course nahi hoti jisko khatam kara ja sake cp is a sport isme parctice kar karke skill develop karni padthi he or practice se aage badte he isme itne topics bhot he beginner ke liye or thoda or karna he to dp me khud specialist tak poch gaya hu
@@samagrapathak3854 kya mai love babbar bhaiya ka C++ DSA Course dekhke pura practise krke khatm krne k baad inn luv bhaiya k CP wale playlist ko shuru karu??ya fir directly idhar se hi shuru karu??am in 1st sem and dont know c of coding right now pls guide me bro😊😊😊
@@harry-cf4ii yahi se srart karo or fir practice karo basic questions ki hackerrank pe jake or jo college me assignment questions mile wo
yellow heart
💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛💛
Giving wrong output in leetcode
It's not daijakstra it's pronounced daikstra
😂🤣
Thanx bhaiya
💛💛💛💛💛💛💛
💛
💕
💛💛💛💛💛
yellow heart
💛🌞⭐🟡🌝🍯
💛💛💛💛💛💛
💛💛
💛💛💛💛
💛
💛💛💛💛
💛💛💛💛
🧡
💛
💛💛💛💛💛
💛💛💛
💛💛💛💛💛