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