dijkstra's algorithm source code c++ code example

Example 1: dijkstra in c++

void dijkstra(int s) {
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  for (int i=0; i<N; i++) dist[i] = INF;
  dist[s] = 0;
  pq.push(make_pair(0, s));
  while (!pq.empty()) {
    pair<int, int> front = pq.top();
    pq.pop();
    int w = front.first, u = front.second;
    if (w > dist[u]) continue;
    for (int i=0; i<adj[u].size(); i++) {
      pair<int, int> v = adj[u][i];
      if (dist[v.first] > dist[u] + v.second) {
        dist[v.first] = dist[u] + v.second;
        pq.push(make_pair(dist[v.first], v.first));
      }
    }
  }
}

Example 2: dijkstra algorithm c++

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

int main()
{
	int n = 9;
	
	int mat[9][9] = { { 100,4,100,100,100,100,100,8,100}, 
                      { 4,100,8,100,100,100,100,11,100}, 
                      {100,8,100,7,100,4,100,100,2}, 
                      {100,100,7,100,9,14,100,100,100}, 
                      {100,100,100,9,100,100,100,100,100}, 
                      {100,100,4,14,10,100,2,100,100}, 
                      {100,100,100,100,100,2,100,1,6}, 
                      {8,11,100,100,100,100,1,100,7}, 
                      {100,100,2,100,100,100,6,7,100}};
	
	int src = 0;
	int count = 1;
	
	int path[n];
	for(int i=0;i<n;i++)
		path[i] = mat[src][i];
	
	int visited[n] = {0};
	visited[src] = 1;
	
	while(count<n)
	{
		int minNode;
		int minVal = 100;
		
		for(int i=0;i<n;i++)
			if(visited[i] == 0 && path[i]<minVal)
			{
				minVal = path[i];
				minNode = i;
			}
		
		visited[minNode] = 1;
		
		for(int i=0;i<n;i++)
			if(visited[i] == 0)
				path[i] = min(path[i],minVal+mat[minNode][i]);
					
		count++;
	}
	
	path[src] = 0;
	for(int i=0;i<n;i++)
		cout<<src<<" -> "<<path[i]<<endl;
	
	return(0);
}