BFS sau Dijkstra: muchii puține versus cost minim

BFS înseamnă Breadth-First Search, adică parcurgere în lățime. Algoritmul explorează un graf pe niveluri folosind o coadă: nodurile descoperite mai devreme sunt prelucrate mai devreme. Într-un graf fără costuri, nivelul dă numărul minim de muchii de la sursă.

Ce măsoară distanța

O muchie este o legătură între două noduri. Dacă fiecare traversare are același cost pozitiv, minimizarea numărului de muchii minimizează și costul total. Dacă muchiile au costuri diferite, cele două obiective se pot separa.

Ia nodurile A,B,C. Muchia directă A-C costă 10, iar A-B și B-C costă fiecare 1. Drumul direct are o muchie, dar cost 10. Drumul prin B are două muchii și cost total 2.

Ce găsește BFS în exemplu

BFS descoperă C la nivelul 1, deoarece există muchia directă. Răspunsul este corect pentru întrebarea „câte muchii sunt necesare minimum?”. Nu este răspunsul la întrebarea „care este suma minimă a costurilor?”.

Nu repari această diferență doar adunând costuri în loc să mărești nivelul cu unu și păstrând regula primei descoperiri. Ordinea unei cozi obișnuite nu garantează că primul drum ponderat descoperit este cel mai ieftin.

Muchia directă A-C costă 10, iar A-B și B-C costă câte 1. BFS minimizează numărul de muchii; drumul de cost minim este A-B-C, cu cost 2.Mărește schema ↗

Ce schimbă Dijkstra

Algoritmul Dijkstra lucrează cu distanțe estimate și alege pentru finalizare nodul accesibil cu cea mai mică distanță curentă. El este potrivit pentru muchii cu costuri nenegative. O implementare frecventă folosește o coadă de priorități, care selectează după cost, nu după momentul introducerii.

Costurile negative nu intră în această garanție. Dacă apar, trebuie analizată altă metodă și chiar existența unui cost minim finit. Alegerea algoritmului începe cu condițiile asupra costurilor.

Verifică și reprezentarea rezultatului

O destinație inaccesibilă trebuie distinsă de o destinație aflată la distanța zero. Pentru reconstruirea drumului, păstrezi și predecesorii, nu doar valoarea distanței. Aceste informații sunt separate de modul în care alegi următorul nod.

Testează un drum direct scump și unul indirect ieftin, apoi un graf în care toate muchiile au cost 1. În al doilea caz, rezultatele de distanță ale celor două abordări trebuie să coincidă pentru nodurile accesibile.

Continuă cu parcurgerile grafurilor, algoritmul Dijkstra și reprezentarea grafurilor.

Întrebări frecvente

Când găsește BFS drumul de cost minim?

BFS, parcurgerea în lățime, minimizează numărul de muchii. Acest lucru minimizează și costul când toate muchiile au același cost pozitiv; pentru costuri diferite nu este suficient în general.

Când folosesc algoritmul Dijkstra?

Pentru drumuri de cost minim într-un graf cu costuri nenegative ale muchiilor. El selectează următoarea distanță minimă provizorie, folosind de obicei o coadă de priorități.

Funcționează Dijkstra dacă există muchii cu cost negativ?

Nu există garanția generală de corectitudine în această situație. Trebuie ales un algoritm potrivit structurii grafului și verificat dacă există cicluri negative relevante pentru drumurile cerute.