Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
feat: python impl for 0-1 BFS#1380
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
| === "C++" | ||
| ```cpp | ||
| d.assign(n, INF); | ||
| d[s] = 0; | ||
| set<pair<int, int>> q; | ||
| q.insert({0, s}); | ||
| while (!q.empty()) { | ||
| int v = q.begin()->second; | ||
| q.erase(q.begin()); | ||
| for (auto edge : adj[v]) { | ||
| int u = edge.first; | ||
| int w = edge.second; | ||
| if (d[v] + w < d[u]) { | ||
| q.erase({d[u], u}); | ||
| d[u] = d[v] + w; | ||
| q.insert({d[u], u}); | ||
| } | ||
| } | ||
| } |
adamant-pwnOct 24, 2024 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| === "C++" | |
| ```cpp | |
| d.assign(n, INF); | |
| d[s] = 0; | |
| set<pair<int, int>> q; | |
| q.insert({0, s}); | |
| while (!q.empty()) { | |
| int v = q.begin()->second; | |
| q.erase(q.begin()); | |
| for (auto edge : adj[v]) { | |
| int u = edge.first; | |
| int w = edge.second; | |
| if (d[v] + w < d[u]) { | |
| q.erase({d[u], u}); | |
| d[u] = d[v] + w; | |
| q.insert({d[u], u}); | |
| } | |
| } | |
| } | |
| === "C++" | |
| ```cpp | |
| d.assign(n, INF); | |
| d[s] = 0; | |
| priority_queue<pair<int, int>> q = {{0, s}}; | |
| while (!empty(q)) { | |
| int [dv, v] = q.top(); | |
| q.pop(); | |
| if (-dv == d[v]) { | |
| for (auto [u, w] : adj[v]) { | |
| if (d[v] + w < d[u]) { | |
| d[u] = d[v] + w; | |
| q.insert({-d[u], u}); | |
| } | |
| } | |
| } | |
| } |
Probably best to make this consistent with Python then. Also remove the comment about "set" above if this is incorporated.
| vector<int> d(n, INF); | ||
| d[s] = 0; | ||
| deque<int> q; | ||
| q.push_front(s); | ||
| while (!q.empty()) { | ||
| int v = q.front(); | ||
| q.pop_front(); | ||
| for (auto edge : adj[v]) { | ||
| int u = edge.first; | ||
| int w = edge.second; | ||
| if (d[v] + w < d[u]) { | ||
| d[u] = d[v] + w; | ||
| if (w == 1) | ||
| q.push_back(u); | ||
| else | ||
| q.push_front(u); | ||
| } | ||
| } | ||
| } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| vector<int> d(n, INF); | |
| d[s] = 0; | |
| deque<int> q; | |
| q.push_front(s); | |
| while (!q.empty()) { | |
| int v = q.front(); | |
| q.pop_front(); | |
| for (auto edge : adj[v]) { | |
| int u = edge.first; | |
| int w = edge.second; | |
| if (d[v] + w < d[u]) { | |
| d[u] = d[v] + w; | |
| if (w == 1) | |
| q.push_back(u); | |
| else | |
| q.push_front(u); | |
| } | |
| } | |
| } | |
| vector<int> d(n, INF); | |
| d[s] = 0; | |
| deque<int> q = {s}; | |
| while (!empty(q)) { | |
| int v = q.front(); | |
| q.pop_front(); | |
| for (auto [u, w] : adj[v]) { | |
| if (d[v] + w < d[u]) { | |
| d[u] = d[v] + w; | |
| if (w == 1) | |
| q.push_back(u); | |
| else | |
| q.push_front(u); | |
| } | |
| } | |
| } |
I think it's best to also rewrite C++ code with a newer standard to match the Python style. But could you please test both implementations on one of the example problems in the article? |
Updates? |
Adding python implementation, fixing a minor grammatical error.
Recreating#1336 against the new base (
main).