Implementarea algoritmului uzual Floyd-Warshell este necesară pentru a programa un calcul paralel al acestei sarcini folosind biblioteca MPI. Voi scrie un raport despre rezultatele paralelizării destul de curând (sper foarte mult pentru asta). Și acum să vorbim despre algoritmul standard al lui Floyd-Warshell.
Esența algoritmului Floyd-Worshell
După cum am menționat, algoritmul este conceput pentru a găsi cele mai scurte căi între toate nodurile din grafic. De fapt, este o simplă căutare a tuturor căilor, iar alegerea lor este cea mai mică. Căutarea este efectuată de așa-numita "matrice de adjunct" a dimensiunii NxN, unde N este numărul de vârfuri ale graficului.
La intersecția liniei i și a coloanei j a matricei este valoarea greutății marginii de la vârful i până la punctul j. Diagonala principală a matricei de adiacență este întotdeauna zero, deoarece nu există margini de la punctul vertex i în graficul i. În cazul în care nu există muchii între vârfuri, infinitatea condiționată (INF) va fi în matrice.
Implementarea algoritmului Floyd-Worshell
Căutarea celei mai mici distanțe se realizează prin căutarea succesivă a tuturor căilor. În trei cicluri, exteriorul alege vârful prin care încercăm să găsim cea mai bună cale. Cele două perechi interioare sortează perechi de vârfuri între care căutăm distanța minimă.
Matricea de adjuvant este stocată cel mai convenabil într-un fișier în următoarea formă: prima linie este numărul de vârfuri, apoi matricea însăși. Ca o infinitate de lungă distanță (INF, atunci când nodurile nu sunt conectate printr-o margine) ia o constantă specifică. În implementarea mea, este de 101, ceea ce înseamnă că greutatea maximă a marginii nu poate fi mai mare de 100.
Exemplu de fișier matrice
Codul sursă al algoritmului
Un exemplu de lucru cu un algoritm
concluzie
Algoritmul uzual Floyd-Warshell este implementat foarte simplu, dar funcționează foarte mult pe matrice mari. Ideal candidat pentru a le da bibliotecii MPI. Pentru ziua de azi, am totul, vă mulțumesc pentru atenție!