APA lab4 - Bagrin

Extras din document

2.2 Determinarea celor mai scurte drumuri intr-un graf Fie G = un graf orientat, unde V este mulţimea vârfurilor şi A este mulţimea arcelor. Fiecărui arc i se asociază o lungime nenegativă. Să se calculeze lungimea celui mai scurt drum între fiecare pereche de varfuri. Vom presupune că vârfurile sunt numerotate de la 1 la n şi că matricea L dă lungimea fiecărui arc: L[i, i] = 0, L[i, j] 0 pentru i j, L[i, j] = dacă arcul (i, j) nu există. Principiul optimalităţii este valabil: dacă cel mai scurt drum de la i la j trece prin varful k, atunci porţiunea de drum de la i la k, cât şi cea de la k la j, trebuie să fie, de asemenea, optime. Construim o matrice D care să conţină lungimea celui mai scurt drum între fiecare pereche de vârfuri. Algoritmul de programare dinamică iniţializează pe D cu L. Apoi, efectuează n iteraţii. După iteraţia k, D va conţine lungimile celor mai scurte drumuri care folosesc ca vârfuri intermediare doar vârfurile din {1, 2, ..., k}. După n iteraţii, obţinem rezultatul final. La iteraţia k, algoritmul trebuie să verifice, pentru fiecare pereche de vârfuri (i, j), dacă există sau nu un drum, trecând prin varful k, care este mai bun decât actualul drum optim ce trece doar prin vârfurile din {1, 2, ..., k Dk matricea D după iteraţia k. Verificarea necesară este atunci: Dk[i, j] = min(Dk-1[i, j], Dk-1[i, k] Dk-1[k, j]) unde s-a facut uz de principiul optimalităţii pentru a calcula lungimea celui mai scurt drum faţă de k. Implicit, s-a considerat că un drum optim care trece prin k nu poate trece de două ori prin k. Acest algoritm simplu este datorat lui Floyd (1962): function Floyd(L[1 .. n, 1 .. n]) 1: array D[1 .. n, 1 .. n] 2: D L 3: for k 1 to n do 4: for i 1 to n do 5: for j 1 to n do 6: D[i, j] min(D[i, j], D[i, kD[k, j]) return D Se poate deduce că algoritmul lui Floyd necesită un timp în O(n3). Un alt mod de a rezolva această problemă este să se aplice algoritmul Dijkstra prezentat mai sus de n ori, alegând mereu un alt vârf sursă. Se obtine un timp în n O (n2), adică tot în O (n3). Algoritmul lui Floyd, datorită simplităţii lui, are însă constanta multiplicativă mai mică, fiind probabil mai rapid în practică Dijkstra : #include #include #include #include #include using namespace std;