Graful ponderat
Definiţie: Considerăm un graf G=(X,U) şi o funcţie f:U R+ care asociază fiecărei muchii (arc) un număr real pozitiv (care poate avea semnificaţia de cost, distanţă, timp, durată).
Definiţie Un graf G=(X,U) pentru care s-a definit o funcţie cost se numeşte graf ponderat.
Definiţie Un graf G=(X,U) pentru care s-a definit o funcţie cost se numeşte graf ponderat.
1. Matricea costurilor
Algoritmul pentru crearea matricei costurilor -se citește pentru fiecare muchie (arc) etichetele extremităţilor ei şi costul asociat.
2. Algoritmi pentru determinarea costului minim (maxim)
În aplicaţiile economice această valoare poate fi:
- lungimea drumului dintre două localităţi;
- costul parcurgerii rutei reprezentate prin arcul corespunzător;
- durata parcurgerii rutei respective;
- cantitatea transportată pe ruta respectivă;
- capacitatea maximă a rutei respective;
- câştigul realizat prin trecerea de la o stare la alta a sistemului;
- consum de energie pentru efectuarea trecerii respective;
- punctaj realizat etc.
S-au elaborat o mulţime de algoritmi, fiecare fiind cel mai eficace în anumite cazuri.
1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);
2. Algoritmi prin ajustări succesive: (Ford);
3. Algoritmi prin inducţie (Dantzig);
4. Algoritmi prin ordonare prealabilă a vârfurilor grafului;
5. Algoritmi prin extindere selectivă (Dijkstra).
În aplicaţiile economice această valoare poate fi:
- lungimea drumului dintre două localităţi;
- costul parcurgerii rutei reprezentate prin arcul corespunzător;
- durata parcurgerii rutei respective;
- cantitatea transportată pe ruta respectivă;
- capacitatea maximă a rutei respective;
- câştigul realizat prin trecerea de la o stare la alta a sistemului;
- consum de energie pentru efectuarea trecerii respective;
- punctaj realizat etc.
S-au elaborat o mulţime de algoritmi, fiecare fiind cel mai eficace în anumite cazuri.
1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);
2. Algoritmi prin ajustări succesive: (Ford);
3. Algoritmi prin inducţie (Dantzig);
4. Algoritmi prin ordonare prealabilă a vârfurilor grafului;
5. Algoritmi prin extindere selectivă (Dijkstra).
2.1. Algoritmul Roy-Floyd
Algoritmul foloseşte un principiu asemănător cu cel utilizat în construirea matricei drumurilor a lui Roy-Warshall: găsirea drumului optim între două noduri oarecare i şi j prin acoperirea drumurilor optime care îl compun şi care trec prin nodurile k se face prin transformarea matricei costurilor.
Algoritmul foloseşte un principiu asemănător cu cel utilizat în construirea matricei drumurilor a lui Roy-Warshall: găsirea drumului optim între două noduri oarecare i şi j prin acoperirea drumurilor optime care îl compun şi care trec prin nodurile k se face prin transformarea matricei costurilor.
Descoperirea drumului de cost minim:
-dacă lungimea drumului minim dintre nodurile i şi j este egală cu suma dintre lungimile minime a două drumuri care trec printr-un nod intermediar k (a[i][j]=a[i][k]+a[k][j]), atunci nodul k face parte din drumul de lungime minimă de la i la j. ->se foloseşte strategia divide et impera.
-dacă lungimea drumului minim dintre nodurile i şi j este egală cu suma dintre lungimile minime a două drumuri care trec printr-un nod intermediar k (a[i][j]=a[i][k]+a[k][j]), atunci nodul k face parte din drumul de lungime minimă de la i la j. ->se foloseşte strategia divide et impera.
Complexitatea algoritmului Roy Floyd -> O(n3)+O(nxlg2n)=O(n3+nxlg2n).
2.2. Algoritmul Dijkstra -construieşte drumurile cu
cost minim care pornesc de la un nod de plecare x – nodul sursă – până la
fiecare nod din graful G=(X,U).
-este cautarea treptată: – un drum minim nu poate avea mai mult de n-1 arce.
-este cautarea treptată: – un drum minim nu poate avea mai mult de n-1 arce.
Implementarea algoritmului
Complexitatea algoritmului Dijkstra -> O(n x lg2n).