Jasne jest, że wynik będzie lasem, bowiem gdybyśmy mieli cykl to przez usunięcie dowolnej krawędzi można go poprawić.
Jeśli las ten nie jest spójny, to łatwo zauważyć, że składać się będzie z dwóch najkrótszych ścieżek z a do b i c do d. Wagę takiego rozwiązania łatwo obliczyć algorytem Dijkstry w O(|V| log |V| + |E|).
Jeśli las jest spójny (= jest drzewem), to widać, że składa się z najkrótszej ścieżki pomiędzy pewnymi u i v (przy czym może być u=v), a wierzchołki a, b, c i d połączone są najktószą ścieżką albo z u albo też z v. Zwracam uwagę, że najlepsze może być zarówno rozwiązanie, w którym a i c łączą się z u, a b i d z v oraz takie, gdzie z u połączone są a i d, a z v łączą się b i c.
Rozwiąznie w czasie O(|V| log |V| + |E|) może więc sprawdzić wynik dla każdego możliwego wyboru u i v. Wymaga to uprzedniego obliczenia długości najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w czasie O(|V|(|V| log |V| + |E|)), a następnie sprawdzenia stałej liczby opcji dla każdego doboru u i v.
Pokażę teraz bardziej efektywne rozwiązanie. Załóżmy, że chcemy znaleźć optymalne rozwiązanie, w którym do wierzchołka u podłączone są ścieżki od wierzchołków a i c, zaś do v - ścieżki od b i d. Na początku obliczamy odległości od wierzchołków a, b, c i d do wszystkich wierzchołków w grafie. To wymaga czterokrotnego użycia algorytmu Dijkstry i daje się zrobić w czasie O(|V| log |V| + |E|). Oznaczmy przez Dx(y) odległość od x do y. Teraz dodamy do grafu dwa wierzchołki s i t. Wierzchołek s połączymy skierowanymi krawędziami ze wszystkimi wierzchołkami w grafie, przy czym wagę krawędzi sw ustalimy na Da(w)+Dc(w). Podobnie, z każdego wierzchołka w grafie wstawimy krawędź do t, a krawędzi wt przypiszemy wagę Db(w)+Dd(w).
Krawędzie sw odpowiadają więc pójściu z a i b jednocześnie po najkrótszych ścieżkach do w, podobnie dla wt. W tak utworzonym grafie szukamy najkrótszej ścieżki z s do t. Odpowiada ona optymalnemu rozwiązaniu dla aktualnie rozpatrywanego przypadku. Ostateczny wynik prosto odzyskać można w czasie O(|E|).