n8118's blog

By n8118, history, 5 years ago, In English

I have learnt Dijkstra's recently and couldn't implement it effectively. Can some one post your Dijkstra's algo implementation in (c or c++) using stl's. I will use it as reference to implement my code. Thanks in advance..

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, You can try this question : EZDIJKST, it's a direct implementation of the algorithm. You can refer My Solution which uses STL set for reference.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my typical implementation of Dijkstra using C++11 and priority_queue: Dijkstra (this code finds the shortest path from node 1 to all other nodes)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    why you use if(dis>d[u]) continue?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because otherwise it would simply be a BFS that keeps going only when new distance would be lower than current minimum distance for the node, and that would be very slow in most cases.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello!

First of all, I would suggest you to write your own version of the code (for testing you have 20C — Dijkstra? problem here on Codeforces), because you will learn how the algorithm works and how to use it. However I will give you my code :). Keep in mind you can find more versions of Dijkstra on geekforgeeks, e-maxx, youtube, ...

Here is my Dijkstra template: https://github.com/Sprdalo/Compete/blob/master/dijkstra.sublime-snippet

To see how to use it go to my submit for this problem which is given here.

»
15 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Checked with C. Dijkstra?.

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

#define debug(x) cout<<#x<<" is "<<endl

using ll = long long;

#define x first
#define y second

template <typename T>
struct Dijkstra {

	int node,edge;
	vector< vector< pair<int,T> > > adj;
	vector< T > level;
	vector<int> parent;

	Dijkstra(int _node, int _edge) : node(_node), edge(_edge) {
		vector<int>(node+1).swap(parent);
		vector<T>(node+1, numeric_limits<T>::max()).swap(level);
		vector< vector< pair<int,T> > > (node+1).swap(adj);
	}

	void add_edge(int u, int v, T w) {
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}

	void traverse(int src) {

		level[src] = 0;
		set< pair<T,int> > s {{0,src}};
		parent[src] = -1;

		while(not s.empty()) {
			auto it = *s.begin();
			int cur_node = it.y;
			T cur_level = it.x;
			s.erase(s.begin());

			for(auto u : adj[cur_node]) {
				if(level[u.x] - u.y > cur_level) {
					level[u.x] = cur_level + u.y;
					parent[u.x] = cur_node; 
					s.insert({level[u.x],u.x});
				}
			}
		}
	}

	void print_path(int x) {

		if(level[x] == numeric_limits<T>::max()) {
			cout<<"-1\n";
			return;
		}

		if(x == -1){
			return;
		}

		print_path(parent[x]);
		cout<<x<<" ";

	}

};


int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	int node,edge;
	cin>>node>>edge;

	Dijkstra<ll> d(node,edge);


	while(edge--){
		int x,y;
		ll w;
		cin>>x>>y>>w;
		d.add_edge(x,y,w);
	}

	d.traverse(1);
	d.print_path(node);

	return 0;
}
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Suggest you to put the code into the spoiler
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://github.com/okwedook/olymp/blob/master/Dijkstra.cpp

This is an actually fast and memory efficient (and also veeery short) implementation. It uses a few template features I use, but you can look at template.cpp in the same repo.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your solution, I dont know I can take the path like that. But can I ask this question

    If we only need to calculate the distance without taking the path. Is this the optimized code or we can still improve it ?

    My code
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Your code uses pairs to store the set. It does actually increase memory usage (I'm only storing the indices) and time usage (as you are also comparing pairs, while I do only one comparison), But you should test your code, it seems pretty neat.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is "neat". Is it mean it is almost similar ?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          It's good in my opinion.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            How about prim algorithm. How do you implement without using heap of pair ?

            prim()
            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              You can use the same idea as used in my Dijkstra imple. Just store the indices of unused vertices and compare them using a custom comparator.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi! Why are we making flag false in line 16? Can you please give an example of such a case.

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Dijkstra - priority_queue implementation
Dijkstra - Set implementation
SPFA - Queue implementation
  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    SPyofgame In your priority queue implementation , priority_queue<pi, vpi, less > pq , In this line why you use less ? Maybe we should use greater. Isn't ?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup, it should be greater, thanks for reminding me. For some reasons I push wrong code :'(

»
2 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define inf 999999999999
using namespace std;
ll n,m;
ll dist[1000009],par[1000009];

void dij(vector<pair<ll,ll> > graph[])
{
	ll i;
	set < pair<ll,ll> > s;
	s.insert(mp(0,1));
	
	for(i=1;i<=n;i++)
	{
		dist[i]=inf;
	}
	dist[1]=0;
	par[1]=0;
	while(!s.empty())
	{
		set <pair<ll,ll> > :: iterator itr;
		itr=s.begin();	
		ll u=itr->s;
		s.erase(s.begin()); 
		for(i=0;i<graph[u].size();i++)
		{
			ll wn=graph[u][i].f;
			ll v=graph[u][i].s;
			
			if(dist[v]>dist[u]+wn)
			{
				if(dist[v]!=inf)
				{
					s.erase(s.find(mp(dist[v],v)));
				}
				dist[v]=dist[u]+wn;
				s.insert(mp(dist[v],v));
				par[v]=u;
			}
			
		}
	}
	
	
}
main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	ll i;
	vector<pair<ll,ll> > graph[n+1];
	for(i=1;i<=m;i++)
	{
		ll a,b,w;
		cin>>a>>b>>w;
		graph[a].pb(mp(w,b));
		graph[b].pb(mp(w,a));
	}
	dij(graph);
	if(dist[n]==inf)
		cout<<"-1";
	else
	{
	vector<ll> v;
	i=n;
	v.pb(i);
	while(i!=1)
	{
		v.pb(par[i]);
		i=par[i];	
	}
	for(i=v.size()-1;i>=0;i--)
		cout<<v[i]<<" ";
	cout<<endl<<dist[n];
}
	
}
	

»
2 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Dijkstra's (CP-Algorithms)

Take a look at the priority queue based implementation. You could probably modify it a bit to make it shorter to code.

Dijkstra's With Path Printing

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I use this implementation. It is from this book.

for (int i = 1; i <= n; i++) distance[i] = INF;
distance[x] = 0;
q.push({0,x});
while (!q.empty()) {
    int a = q.top().second; q.pop();
    if (processed[a]) continue;
    processed[a] = true;
    for (auto u : adj[a]) {
        int b = u.first, w = u.second;
        if (distance[a]+w < distance[b]) {
            distance[b] = distance[a]+w;
            q.push({-distance[b],b});
        }
    }
}
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell me how can you modify it for Prim's Algorithm?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

cf rating doesnt matter

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
I think it will help you
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro if you write your code in between "~~~" (without quotes) your text will be detected as code and it will look neat as you see in editorials. Or you can use blocks from "code drop down" (left to codeforces sysmbol) in codeforces's editor.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

use https://cp-algorithms.com/ u will find almost all u need

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;

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

void Dijkstra(vector<pair<int,int>> G[], int n, int source) {
	priority_queue<pair<int,int>> pq; // <dist,vertex>
	int dist[n];
	for(int i=0; i<n; i++) dist[i] = INT_MAX;

	pq.push(make_pair(0, source));
	dist[source] = 0;

	while(!pq.empty()) {
		int v = pq.top().second;
		pq.pop();
		for(int x=0; x<G[v].size(); x++) {
			int weight = G[v][x].second;
			if(dist[G[v][x].first] > dist[v] + weight) {
				dist[G[v][x].first] = dist[v] + weight;
				pq.push(make_pair(dist[v] + weight, G[v][x].first));
			}
		}
	}
	printf("Vertex   Distance from Source\n"); 
    for (int i = 0; i < n; ++i) 
        printf("%d \t\t %d\n", i, dist[i]);
}

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