Pentru doua noduri $P,Q$ din graf, vom defini $d(P,Q)$ ca fiind drumul de cost minim de la $P$ la $Q$. Pe noi ne intereseaza sa gasim un nod $X$ astfel incat suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima. Pentru a realiza acest lucru trebuie sa calculam pentru orice nod $K$ din graf $d(A,K),d(B,K) si d(C,K)$. Putem face acest lucru folsind 'Algoritmul lui Dijsktra':/problema/dijkstra. Nodul solutie va fi acel nod $X$ cu proprietatea ca suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima.

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 disjuncte. 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.

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.

Complexitatea solutiei este O(MlogN).

Complexitate finala va fi O(MlogN).