→ Обратите внимание

До соревнования
Codeforces Round 1123 (Div. 2)
45:16:03
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя n8118

Dijkstra's implementation in c++

Автор n8118, история, 11 лет назад, По-английски

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..

dijkstra, graph, c++, stl

n8118
11 лет назад
37

Комментарии (30)

Показать архивные | Написать комментарий?

SomeRandomGuy

11 лет назад, скрыть # |

http://e-maxx.ru/algo/dijkstra

→ Ответить

achaitanyasai

11 лет назад, скрыть # |

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.

→ Ответить

tenshi_kanade

11 лет назад, скрыть # |

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)

→ Ответить

shubham_n

6 лет назад, скрыть # ^ |

-8

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

→ Ответить

tenshi_kanade

6 лет назад, скрыть # ^ |

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.

→ Ответить

OmaeWaMouShenDeiru

11 лет назад, скрыть # |

http://ideone.com/xEBzsj

→ Ответить

Sprdalo

8 лет назад, скрыть # |

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.

→ Ответить

arjun17

7 лет назад, скрыть # |

-8

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

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

Suggest you to put the code into the spoiler

Done

→ Ответить

okwedook

6 лет назад, скрыть # |

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.

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

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

vector<int> dist;
vector<bool> mark;
void dijkstra(int s)
{
    fill(dist.begin(), dist.end(), INF);
    fill(mark.begin(), mark.end(), false);
    
    priority_queue<pi, vpi, less<pi> > pq;
    pq.push({dist[s] = 0, s});
    while(!pq.empty()){
        int u = pq.top().se;
        pq.pop();
        
        if (!mark[u]) mark[u] = true; else continue;
        for (pi v : G[u])
            if (dist[v.fi] > dist[u] + v.se)
                pq.push({dist[v.fi] = dist[u] + v.se, v.fi});
    }
}

→ Ответить

okwedook

6 лет назад, скрыть # ^ |

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.

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

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

→ Ответить

okwedook

6 лет назад, скрыть # ^ |

It's good in my opinion.

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

← Rev. 3 →

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

prim()


vector<int> dis;
int prim()
{
    fill(all(dis), +INF);   
    int res = 0;
    
    priority_queue <pi, vpi, greater <pi> > S;
    S.push({dis[1] = 0, 1});
    while (!S.empty()) {
        pi u = S.top();
        S.pop();
        if (dis[u.se] != u.fi) continue;
        
        res += dis[u.se];
        dis[u.se] = 0;
        for (pi v : G[u.se]) 
            if (dis[v.fi] > v.se)
                S.push({dis[v.fi] = v.se, v.fi});
    }
    return res;
}

→ Ответить

okwedook

6 лет назад, скрыть # ^ |

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.

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

Ok thanks for your method

→ Ответить

prateek_aries

6 лет назад, скрыть # ^ |

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

→ Ответить

okwedook

6 лет назад, скрыть # ^ |

It's a bug:) Must be i.f instead of f.

→ Ответить

SPyofgame

6 лет назад, скрыть # |

← Rev. 3 →

Dijkstra - priority_queue implementation

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pi> vpi;
typedef vector<vi> vmi;
typedef vector<vpi> vmpi;

const int INF = 1e9 + 19;
const int LIM = 1e5 + 15;

int n, m;
vmpi G;
vb mark;
vi dist;

void dijkstra(int s)
{
    fill(all(dist), +INF);
    fill(all(mark), false);
    
    priority_queue<pi, vpi, less<pi> > pq;
    pq.push({dist[s] = 0, s});
    while (!pq.empty()) {
        int u = pq.top().se;
        pq.pop();
        
        if (mark[u]) continue; else mark[u] = true;
        for(auto v : G[u])
        {
            if (dist[v.fi] > dist[u] + v.se)
            {
                dist[v.fi] = dist[u] + v.se;
                pq.push({dist[v.fi], v.fi});
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    G.resize(n + 1);
    mark.assign(n + 1, false);
    dist.resize(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;
        G[u].pb({v, c});
    }

    int s, t;
    cin >> s >> t;

    dijkstra(s);
    if (dist[t] == INF)
        cout << "There is no path from " << s << " to " << t;
    else 
        cout << "Min distance(" << s << " -> " << t << ") = " << dist[t];
        
    return 0;
}

Dijkstra - Set implementation

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pi> vpi;
typedef vector<vi> vmi;
typedef vector<vpi> vmpi;

const int INF = 1e9 + 19;
const int LIM = 1e5 + 15;

int n, m;
vmpi G;
vb mark;
vi dist;

void dijkstra(int s){
    fill(dist.begin(),dist.end(), LIM);
    
    set<pi> S;
    S.insert({dist[s] = 0, s});
    while(!S.empty()){
        int u = S.begin() -> se;
        S.erase(S.begin());
        
        for(auto v : G[u])
        {
            if(dist[v.fi] > dist[u] + v.se)
            {
                S.erase({dist[v.fi], v.fi});
                dist[v.fi] = dist[u] + v.se;
                S.insert({dist[v.fi], v.fi});
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    G.resize(n + 1);
    mark.assign(n + 1, false);
    dist.resize(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, s, c;
        cin >> u >> s >> c;
        G[u].pb({s, c});
    }

    int s, t;
    cin >> s >> t;

    dijkstra(s);
    if (dist[t] == INF)
        cout << "There is no path from " << s << " to " << t;
    else 
        cout << "Min distance(" << s << " -> " << t << ") = " << dist[t];
        
    return 0;
}

SPFA - Queue implementation

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vmi;
typedef vector<pi> vpi;
typedef vector<vpi> vmpi;

const int INF = 1e9 + 19;

int n, m;   
vmpi G;
vb mark;
vi dist;

void spfa(int s)
{
    fill(dist.begin(), dist.end(), INF);
    fill(mark.begin(), mark.end(), false);
    
    mark[s] = true;
    dist[s] = 0; 
    
    deque<int> S(1, s);
    while (!S.empty())
    {
        int u = S.front();
        S.pop_front();
        mark[u] = false;
        
        for (int i = 0; i < G[u].size(); ++i)
        {
            int v = G[u][i].fi;
            int w = G[u][i].se;

            if (dist[v] > dist[u] + w) 
                dist[v] = dist[u] + w;  

            if (!mark[v]) 
            {
                S.push_back(v);
                mark[v] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    G.resize(n + 1);
    mark.assign(n + 1, false);
    dist.resize(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;
        G[u].pb({v, c});
    }

    int s, t;
    cin >> s >> t;

    spfa(s);
    if (dist[t] == INF)
        cout << "There is no path from " << s << " to " << t;
    else 
        cout << "Min distance(" << s << " -> " << t << ") = " << dist[t];
        
    return 0;
}

→ Ответить

Muhammad_mhs

6 лет назад, скрыть # ^ |

← Rev. 2 →

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 ?

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

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

→ Ответить

karankamboj

6 лет назад, скрыть # |

← Rev. 2 →

-15

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

→ Ответить

arujbansal

6 лет назад, скрыть # |

← Rev. 4 →

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

→ Ответить

sarkarasm

6 лет назад, скрыть # |

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

→ Ответить

RD_TheCoder

6 лет назад, скрыть # |

I think it will help you

include <bits/stdc++.h>

using namespace std;

define infinity 1<<30 //2^30

struct node{ int u; int cost; node(int _u, int _cost){ u = _u; cost = _cost; } bool operator < ( const node& p ) const { return cost > p.cost; } //Operator overloading

}; void dijstkra(int n, vectorg[], vectorcost[], int source){

int distance[n+1];
for(int i=1;i<=n;i++) {
    distance[i] = infinity;
}

priority_queue<node>q;
q.push(node(source,0));
distance[source] = 0;

while(!q.empty()){
    node top = q.top();
    q.pop();
    int u=top.u;

    for(int i=0;i<(int)g[u].size();i++){
        int v=g[u][i];

        //Relaxation
        if(distance[u] + cost[u][i] < distance[v]){
            distance[v] = distance[u] + cost[u][i];
            q.push(node(v, distance[v]));
        }
    }
}
for(int i=1;i<=n;i++){
    cout<<source<<" --> "<<i<<" = "<<distance[i]<<endl;
}

} int main(){

vector<int>g[10000], cost[10000]; //this code can handle maximum 10000 nodes
int numNodes, numEdges;
cin>>numNodes>>numEdges;
for(int i=0;i<numEdges;i++){
    int u, v, w;
    cin>>u>>v>>w;
    g[u].push_back(v);
    g[v].push_back(u);
    cost[u].push_back(w);
    cost[v].push_back(w);
}
int source;
cin>>source;
dijstkra(numNodes, g, cost, source);

return 0;

}

→ Ответить

ayushkoul00

4 года назад, скрыть # |

-13

I tried to submit my code of dijkstra's on codeforces C. Dijkstra? but I am running into a weird error. I have detailed my question here on stackoverflow: https://stackoverflow.com/questions/71748407/how-can-a-node-in-dijkstra-be-relaxed-after-it-has-already-been-processed?noredirect=1#comment126796300_71748407

basically, the question is, if I relax a node v, then that means there is no way that node has been processed (i.e. it hasn't been popped from the heap and we haven't found the min dist to that node yet). This means that processed[v] == true should never evaluate to true when we are relaxing the node v. But it does in the testcases of codeforces question

→ Ответить

jerdno

4 года назад, скрыть # ^ |

You comparison approach in PQ might be wrong because you are updating values used for comparison dynamically. As such it might "corrupt" whole data structure. So my advice is: store the distance and index directly in PQ, instead using dist vector.

It is just my guess though (I didn't test it)

→ Ответить

ayushkoul00

4 года назад, скрыть # ^ |

-10

That is not the case because if I comment the if statement my code is accepted. and it is pretty efficient also. and if you see this: https://cp-algorithms.com/graph/dijkstra_sparse.html#:~:text=version%20with%20set.-,Getting,-rid%20of%20pairs

This also suggests to improve the speed and memory by only storing the index of the vertex

→ Ответить

jeroenodb

4 года назад, скрыть # ^ |

If you look closely, cp-algorithms states that using just indices in a c++ priority_queue does not work. This destroys the invariants of the data structure, and after you change the distance array, it will not always give back the "real" minimum element in the priority_queue, making the algorithm now wrong. With an std::set, it is possible, because you can first remove and then reinsert the element that is affected.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.09.2026 20:18:58 (g2).

Десктопная версия, переключиться на мобильную.

При поддержке