Stim ca aloritmul va lua cel putin doua iteratii pentru ca se garanteaza ca exista cel putin o muchie care iese din nodul 1. Pentru ca algoritmul lui Por Costel sa se termine in doua iteratii, trebuie ca doar la prima iteratie sa se produca relaxari ale muchiilor (modificari ale vectorului d). Cand se intra in iteratia a doua trebuie ca in vectorul d sa existe deja valorile drumurilor minime pentru a nu se produce nicio modificare, variabila _ok_ sa ramana cu valoarea 1 si sa nu se mai intre in while a treia oara.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul $x$ catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din $x$). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul $x$ (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia este o astfel de ordonare a $N$-1 muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de $M$@-@$N$+1 muchii pot fi interclasate cu acestea in orice fel.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul $x$ catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din $x$). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul $x$ (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia este o astfel de ordonare a @N-1 muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de M-N+1@ muchii pot fi interclasate cu acestea in orice fel.

Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate O(N*M) chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind algoritmul lui Dijkstra: https://www.youtube.com/watch?v=fTEcL7bw6U4