Trilant

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

Complexitatea solutiei este O(MlogN).