Presupunem ca am ales nodul $X$ cu proprietatea de mai sus. Daca drumurile $(X,A)$ si $(X,B)$ nu ar fi disjuncte, atunci stim sigur ca exista un nod $K$ pe lantul de la $X$ la $A$, astfel incat drumurile $(K,A)$ si $(K,B)$ sunt dijuncte. Inseamna ca pe drumul de la $K$ la $X$, vom numara muchiile care apar de doua ori, rezulta ca $X$ nu ar avea proprietatea ca suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima. Analog daca $(X,A)$ si $(X,C)$ sau $(X,B)$ si $(X,C)$ nu ar fi disjuncte.

Complexitate finala va fi O(MlogN).

Complexitatea solutiei este O(MlogN).