Găsirea celei mai scurte căi între două puncte pe un grafic este o problemă obișnuită în structurile de date, mai ales atunci când avem de-a face cu optimizarea.

Un grafic este o serie de noduri conectate prin margini. Graficele pot fi ponderate (marginile poartă valori) și direcționale (marginile au direcție).

Unele aplicații ale acestui lucru sunt optimizarea traseului de zbor sau 6 grade ale lui Kevin Bacon.

Algoritmul lui Dijkstra

Cea mai comună soluție pentru această problemă este algoritmul lui Dijkstra care actualizează cea mai scurtă cale între nodul curent și toți vecinii săi.

După actualizarea distanței tuturor vecinilor, se deplasează către nodul cu cea mai mică distanță și repetă procesul cu toți vecinii nevizitați. Acest proces continuă până când întregul grafic a fost vizitat.

Imagine a nivelurilor de cod

Pasul 0:

Graficul nostru trebuie configurat astfel încât să putem înregistra valorile necesare. Pe orice margine avem distanța dintre cele două noduri pe care le conectează. Pe orice nod avem distanța sa cea mai mică de nodul de pornire.

Să setăm valoarea pe fiecare nod la infinit pozitiv și să setăm valoarea de pe nodul de pornire la zero.

Pasul 1:

Uită-te la toate nodurile direct adiacente nodului de pornire. Valorile purtate de marginile care leagă startul și aceste noduri adiacente sunt cele mai mici distanțe față de fiecare nod respectiv.

Înregistrați aceste distanțe pe nod – suprascrierea infinitului și, de asemenea, traversați nodurile, ceea ce înseamnă că a fost găsită cea mai scurtă cale a acestora.

Pasul 2:

Selectați unul dintre nodurile care a avut cea mai scurtă cale calculată, vom numi aceasta pivotul nostru. Uită-te la nodurile adiacente acestuia (le vom numi nodurile noastre de destinație) și la distanțele care le separă.

Pentru fiecare nod de destinație:

  • Dacă valoarea din pivot plus valoarea de margine care îl conectează totalizează mai puțin decât valoarea nodului de destinație, atunci actualizați valoarea acestuia, deoarece a fost găsită o nouă cale mai scurtă.
  • Dacă au fost explorate toate rutele către acest nod de destinație, acesta poate fi tăiat.

Pasul 3:

Repetați pasul 2 până când toate nodurile au fost tăiate. Acum avem un grafic în care valorile deținute în orice nod vor fi cea mai mică distanță față de acesta de la nodul de pornire.

Mai multe informatii:

Mai multe despre algoritmul lui Dijkstra

Alți algoritmi de cale mai scurte