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': http://www.infoarena.ro/problema/dijkstra

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

Complexitatea: <tex>O(M*logN)</tex>