Algoritmul Bellman-Ford

Enunţ: Se consideră un graf orientat G=(X,U) şi o funcţie de cost c:U->R. Mulţimea X conţine n vârfuri. Se desemnează un nod p de plecare. Pentru orice nod j∈X se cere determinarea drumului de cost minim de la p la j. Se vor detecta situaţiile în care există circuite de cost negativ care includ nodul p.
Algoritmul Bellman-Ford determină drumurile de cost minim dintre un nod desemnat ca sursă (plecare) şi restul nodurilor accesibile lui chiar dacă există costuri negative pe arce. Aceste rezultate sunt furnizate numai în situaţia în care nodul de plecare nu face parte dintr-un circuit de cost negativ.
Strategia algoritmului este aceea de minimizare succesivă a costului drumului minim de la p la orice nod j din graf (d[j]) până la obţinerea costului minim.
Această operaţie se face prin verificarea posibilităţii ca fiecare arc (i,j)∈U să participe la minimizarea distanţei de la p la j. Operaţia se face cu o trecere completă prin toate arcele grafului.

Condiţia ca distanţa de la p la j să poată fi minimizată prin arcul (i,j) este ca d[j]>d[i]+c[i,j]
Notăm cu n numărul de noduri din graf. Algoritmul efectuează n-1 treceri complete prin mulţimea arcelor grafului (orice drum elementar poate fi format din maxim n-1 arce). În final, existenţa unui circuit negativ face ca la o nouă trecere prin mulţimea arcelor să fie în continuare posibilă minimizarea costului unui drum. În acest caz algoritmul evidenţiază prezenţa circuitului de cost negativ ce cuprinde nodul sursă.

Cod Sursa C++

#include "stdafx.h"
#include<iostream>
#include<stdio.h>
 
using namespace std;
 
#include<conio.h>
 
#define INFINITY 999
 
struct node
{
	int cost;
	int value;
	int from;
}a[5];
 
void addEdge(int am[][5], int src, int dest, int cost)
{
	am[src][dest] = cost;
	return;
}
 
void bell(int am[][5])
{
	int i, j, k, c = 0, temp;
	a[0].cost = 0;
	a[0].from = 0;
	a[0].value = 0;
	for (i = 1; i < 5; i++)
	{
		a[i].from = 0;
		a[i].cost = INFINITY;
		a[i].value = 0;
	}
 
	while (c < 5)
	{
		int min = 999;
		for (i = 0; i < 5; i++)
		{
			if (min > a[i].cost && a[i].value == 0)
			{
				min = a[i].cost;
			}
			else
			{
				continue;
			}
		}
		for (i = 0; i < 5; i++)
		{
			if (min == a[i].cost && a[i].value == 0)
			{
				break;
			}
			else
			{
				continue;
			}
		}
		temp = i;
		for (k = 0; k < 5; k++)
		{
			if (am[temp][k] + a[temp].cost < a[k].cost)
			{
				a[k].cost = am[temp][k] + a[temp].cost;
				a[k].from = temp;
			}
			else
			{
				continue;
			}
		}
		a[temp].value = 1;
		c++;
	}
	cout << "Cost" << "\t" << "Nod sursa" << endl;
	for (j = 0; j < 5; j++)
	{
		cout << a[j].cost << "\t" << a[j].from << endl;
	}
}
 
int main()
{
	int n, am[5][5], c = 0, i, j, cost;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			am[i][j] = INFINITY;
		}
	}
	while (c < 8)
	{
		cout << "Introduceti nodul sursa: ";
		cin >> i;
		cout << "Introduceti nodul destinatie: ";
		cin >> j;
		cout << "Introduceti costul muchiei: ";
		cin >> cost;
		addEdge(am, i, j, cost);
		c++;
	}
	bell(am);
	system("pause");
}
 

Rezultat: