ALGORITMI DIN TEORIA GRAFURILOR - Algoritmul lui Floyd, Warshall

Algoritmi din teoria grafurilor

Multe rezultate din teoria grafurilor sunt cunoscute sub forma unor algoritmi celebri.

Prezentam mai jos doi algoritmi binecunoscuti : algoritmul lui Floyd si algoritmul lui Warshall.

Algoritmul lui Floyd

Algoritmul lui Floyd permite calculul matricii drumurilor de cost minim dintr-un graf pornind de la matricea costurilor muchiilor A.

Daca notam A¹=A, atunci, pentru k>1 se construieste matricea :

A^k[i,j]=min (A^k-1[i,j], A^k-1[i,k]+A^k-1[k,j])

La fiecare pas k, matricea A^k[i,j] va contine cea mai mica distanta dintre i si j prin noduri care nu depasesc valoarea k.

Se observa ca A^k[i,k]= A^k-1[i,k] si A^k[k,j]= A^k-1[k,j] si deci se poate lucra succesiv asupra aceleasi matrici fara a mai folosi indicii k superiori de la A^k..

Implementarea in limbajul C

/determinarea matricii drumurilor de cost minim intr-un graf neorientat

#include<stdio.h>

#include<conio.h>

int c[20][20],n,i,j;

void citire_matrice_costuri(int c[20][20],int n)

}

}

void afisare(int c[20][20],int n)

void floyd(int c[20][20])

void main()

Algoritmul lui Warshall

Implementarea in limbajul C

Algoritmul lui Warshall permite calculul matricii existentei drumurilor dintr-un graf pornind de la matricea de adiacenta A.

Daca notam A¹=A, atunci, pentru k>1 se construieste matricea :

A^k[i,j]= A^k-1[i,j] or (A^k-1[i,k] and A^k-1[k,j])

La fiecare pas k, matricea A^k[i,j] va contine valoarea 1 daca exista un drum de la i la j prin noduri care nu depasesc valoarea k si valoarea o daca un astfel de drum nu exista.. Se observa ca A^k[i,k]= A^k-1[i,k] si A^k[k,j]= A^k-1[k,j] si deci se poate lucra succesiv asupra aceleasi matrici fara a mai folosi indicii k superiori de la A^k..

/determinarea matricii drumurilor intr-un graf neorientat

#include<stdio.h>

#include<conio.h>

int a[20][20],n,i,j;

void citire_matrice_adiacenta(int a[20][20],int n)

}

}

void afisare(int a[20][20],int n)

void warshall(int a[20][20])

void main()