Algoritmul lui Dijkstra
De la Wikipedia, enciclopedia liberă
Algoritmul lui Dijsktra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf. Numele este dat de Edsger Dijkstra, savantul care l-a descoperit.
[modifică] Algoritm
- Se creează o listă cu distanţe, o listă cu nodul anterior, o listă cu nodurile vizitate şi un nod curent.
- Toate valorile din lista cu distanţe sunt iniţializate cu o valoare infinită, cu excepţia nodului de start, care este setat cu 0.
- Toate valorile din lista cu nodurile vizitate sunt setate cu fals.
- Toate valorile din lista cu nodurile anterioare sunt iniţializate cu -1.
- Nodul de start este setat ca nodul curent.
- Se marchează ca vizitat nodul curent.
- Se actualizează distanţele, pe baza nodurilor care pot fi vizitate imediat din nodul curent.
- Se actualizează nodul curent la nodul nevizitat care poate fi vizitat prin calea cea mai scurtă de la nodul de start.
- Se repetă (de la punctul 6) până când toate nodurile sunt vizitate.
