Utilizarea și programarea calculatoarelor 2 - Laborator 13

Calculul drumurilor minime într-un graf

O reprezentare frecventă a grafurilor este cea prin matrici de adiacență: pentru un graf cu n noduri se folosește o matrice A de dimensiune nxn în care elementul A[i][j] e 1 dacă există o muchie de la nodul i la nodul j și 0 în caz contrar. Eventual, în matricea A se pot reține informații mai precise despre muchiile grafului, cum ar fi costul lor (de exemplu distanța, dacă graful are ca noduri localități). În acest caz, trebuie aleasă o valoare specială pentru a reprezenta o muchie inexistentă, de exemplu INFINITY din math.h dacă în matrice reprezentăm distanțe între noduri (numere reale). Dacă graful e neorientat (sensul de parcurgere al unei muchii nu contează, vom avea A[i][j] == A[j][i] oricare ar fi i și j.

Problemă Fiind dat un graf reprezentând o mulțime de localități, cu drumuri de distanțe date între unele dintre ele, determinați pentru fiecare pereche de noduri drumul cel mai scurt (dacă există).

Soluția clasică pentru această problemă (algoritmul Floyd-Warshall) pornește de la observația că dacă A[i][k] + A[k][j] < A[i][j], atunci există un drum mai scurt de la i la j trecând prin k decât cel găsit până în prezent -- caz în care actualizăm pe A[i][j]. Testul efectuează succesiv pentru fiecare nod intermediar k, iar pentru fiecare din acestea, pentru toate perechile i, j.

Implementați algoritmul descris mai sus și rulați programul pentru un graf citit de la intrare (întâi numărul de noduri, iar apoi triplete formate din două noduri și distanța dintre ele). Afișați, la cerere, lungimea drumului minim dintre două noduri introduse de utilizator.


Marius Minea
Last modified: Sun May 23 16:23:40 EEST 2004