Algoritmul lui Djikstra

Aspecte teoretice:

Dându-se un (di)graf G=(V,E) și o funcție de cost C:E→R atașată muchiilor, se cere să se determine drumurile minime (de cost minim) de la un nod i0 la toate nodurile din graf, precum și costurile acestor drumuri.
Pentru rezolvarea problemei se folosește metoda Greedy: se selectează nodurile grafului, unul câte unul, în n-1 pași, în ordinea crescătoare a costului drumului de la nodul de start la ele, într-o mulțime care inițial conține doar nodul de start.
În implementarea algoritmului se folosește un vector Anterior (cu legături de tip “tata”)
cu semnificația: dacă Anterior[i]=k atunci k este nodul anterior nodului i pe drumul minim
de la i0 (nodul de start) la nodul i.
De asemenea, se utilizează doi vectori cu n componente, d și Selectat:

• d[i]=costul minim al drumului de la i0 la i;
• Selectat[i]=True ⇔ nodul i este selectat.
Algoritmul este:
• La început, se selectează i0.
• La fiecare pas p din cei n-1 pași:
∗ se caută nodul i neselectat cu d[i] minim, fie acesta k și se selectează;
∗ se actualizează vectorul d pentru acele noduri i neselectate, dar pentru care fostul d[i]
este mai mare decât d[k]+costul muchiei (i,k); astfel d[i] devine d[k]+C[k,i], iar
Anterior[i]:=k. Așadar, drumul de la i0 la i are ca nod intermediar (exact înainte de i) pe
nodul k.
• La sfârșit, folosind vectorul Anterior, se afișează drumurile de la i0 la fiecare nod i al
grafului, precum și costurile acestor drumuri.

Implementare:

Cod Sursa C++

// DjikstraCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
const int max = 11;
const int infinit = 1000;
int c[11][11];
int i0;
int d[11];
bool selectat[11];
int anterior[11];
int minim, pas, i, j, k, n;
bool gata;
 
void drum(int i)
{
	if (anterior[i] != 0)
	{
		drum(anterior[i]);
		cout << "," << i;
	}
	else
		cout << i;
 
}
 
int main()
{
	cout << "Numarul de varfuri: "; cin >> n;
	for (i = 1; i <= n - 1; i++)
	{
		c[i][i] = 0;
		for (j = i + 1; j <= n; j++)
		{
			cout << "c[" << i << "," << j << "]="; cin >> c[i][j];
			if (c[i][j] == 0)
				c[i][j] = infinit;
			c[j][i] = c[i][j];
		}
	}
	cout << "nodul de start= "; cin >> i0;
	for (i = 1; i <= n; i++)
	{
		selectat[i] = false;
		d[i] = c[i0][i];
		if (d[i]<infinit)
			anterior[i] = i0;
		else
			anterior[i] = 0;
	}
	selectat[i0] = true;
	anterior[i0] = 0;
	d[i0] = 0;
	for (pas = 1; pas <= n - 1; pas++)
	{
		minim = infinit;
		for (i = 1; i <= n; i++)
		if (!selectat[i] && d[i]<minim)
		{
			minim = d[i];
			k = i;
		}
		selectat[k] = true;
		for (i = 1; i <= n; i++)
		if (!selectat[i] && d[k] + c[k][i]<d[i])
		{
			d[i] = d[k] + c[k][i];
			anterior[i] = k;
		}
	}
	for (i = 1; i <= n; i++)
	{
		cout << "Drumul minim de la " << i0 << " la " << i << ": " << endl;
		drum(i);
		cout << endl;
		cout << "Costul sau este " << d[i];
		cout << endl;
	}
	system("pause");
}
 

Exemplu:

Pentru următorul graf:

Se va obține următorul rezultat: