Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate stiintaSa fii al doilea inseamna sa fii primul care pierde - Ayrton Senna





Aeronautica Comunicatii Drept Informatica Nutritie Sociologie
Tehnica mecanica




Informatica


Qdidactic » stiinta & tehnica » informatica
Algoritmi din teoria grafurilor



Algoritmi din teoria grafurilor


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 A1=A, atunci, pentru k>1 se construieste matricea :

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




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

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

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 A1=A, atunci, pentru k>1 se construieste matricea :

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

La fiecare pas k, matricea Ak[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 Ak[i,k]= Ak-1[i,k] si Ak[k,j]= Ak-1[k,j] si deci se poate lucra succesiv asupra aceleasi matrici fara a mai folosi indicii k superiori de la Ak..




/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()








Contact |- ia legatura cu noi -|
Adauga document |- pune-ti documente online -|
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -|
Copyright © |- 2022 - Toate drepturile rezervate -|