• Algorytm BFS(a) przegląda graf zaczynając od wierzchołka a.
• W algorytmie wykorzystuje się kolejkę, do przechowywania wierzchołków, które należy odwiedzić.
• Każdy wierzchołek, który trafia do kolejki jest oznaczany; w programie nadajemy mu wartość col[u] = true.
• Algorytm dodatkowo wyznacza tablicę dist[u], która przechowuje informacje o odległościach odwiedzonych wierzchołków od wierzchołka początkowego a.

#include<vector>
#include<queue>
using namespace std;

vector<int> G[1000001];
bool col[1000001];
int dist[1000001];

// Przeglądanie grafu wszerz
// Obliczamy wartości dist[...] oznaczające
// odległości od wierzchołka 'a'
void bfs(int a)
{
  queue<int> Q;
  Q.push(a); col[a] = true; // wstaw wierzchołek 'a' do kolejki
  dist[a] = 0;
  while( !Q.empty() ) // dopóki kolejka nie jest pusta
  {
    int u = Q.front(); Q.pop();
    for (int i=0; i<G[u].size(); i++)
    {
      int v = G[u][i];
      if ( col[v]==false )
      {
	Q.push(v); col[v] = true;
	dist[v] = dist[u]+1;
      }
    }
  }
}

#include<queue>
#include<vector>
#include<iostream>
using namespace std;

vector< pair<int,int> > G[1000000]; // reprezentacja grafu z wagami

//~~~~~~~~~~~~~~~~~~~~~~~
/** Wczytywanie grafu **/
//~~~~~~~~~~~~~~~~~~~~~~~
int n,m;
cin >> n >> m; // wczytaj liczbę wierzchołków i krawędzi
for (int i=0; i<m; i++)
{
	cin >> a >> b >> c; // wczytaj krawędź a--b z kosztem c
	G[a].push_back( make_pair(b,c) );
	G[b].push_back( make_pair(a,c) );
	// assert( c>=0 ); // upewnij się, że wagi są nieujemne
}

//~~~~~~~~~~~~~~~~~~~~~~~
/** Algorytm Dijkstry **/
//~~~~~~~~~~~~~~~~~~~~~~~~

int  dist[1000000]; // tablica obliczonych odległości od źródła
bool mark[1000000]; // będziemy zaznaczali wierzchołki, które zostały z kolejki usunięte
#define INF 2000000000

priority_queue< pair<int,int> > Q; // kolejka wierzchołków do obsługiwania
// zasada jest taka: w kolejce trzymamy pary (-c, u), gdzie c oznacza koszt
// ścieżki do źródła z wierzchołka o numerze u


void dijkstra(int s) // s = source, czyli numer wierzchołka (źródła)
{
	int u,d;
	
	// inicjalizacja
	for (int u=0; u<n; u++)
	{
		mark[u] = false;
		dist[u] = INF;
	}
	
	dist[s] = 0; // ustawiamy odległość źródła od źródła na zero
	Q.push( make_pair(0,s) ); // wstawiamy wierzchołek s do kolejki

	while( !Q.empty() )
	{
		// wyciągamy wierzchołek nr u, dla którego odległość d od źródła s jest najmniejsza
		u = Q.front().second();
		d = -Q.front().first();
		Q.pop();
		
		if ( mark[u]==true ) continue; // jeśli już go kiedyś usunęliśmy, to możemy nic nie robić, bo na pewno wtedy miał mniejsze d
		mark[u] = true; // oznaczamy, że wierzchołek u został usunięty z kolejki
		
		for (int i=0; i<G[u].size(); i++)
		{
			// rozpatrujemy krawędź u--v z kosztem c
			int v = G[u][i].first(); 
			int c = G[u][i].second();
			
			// jeśli v nie ma jeszcze obliczonej najkrótszej odległości od źródła s,
			// oraz to co ma dotychczas obliczone da się poprawić, to poprawiamy
			if ( !mark[v] && dist[v] > dist[u]+c )
			{
				dist[v] = dist[u]+c;
				Q.push( make_pair(-dist[v],v) ); // i wstawiamy v do kolejki
				// Uwaga: może się więc zdażyć, że v jest kilka razy w kolejce
				// nie przeszkadza nam to, bo razem z v są różne koszty.
				// Gdy będziemy usuwali v z kolejki, to na pewno weźmiemy tego z najmniejszą odległością od źródła
				// Następnych będziemy po prostu pomijali, czyli usuwali nic nie robiąc (patrz na instrukcję continue sprzed 18 wierszy)
			}
		}
	}

}

Prezentacja działania

// deklaracja kolejki priorytetowej Q, w której element top()
// ma najmniejszą wartość
priority_queue<int, vector<int>, greater<int> > Q;