Oznaczmy zbiór wierzchołków grafu  przez  i niech  oznaczają liczbę wierzchołków i krawędzi w grafie. Niech  będą wyróżnionymi wierzchołkami. Szukany optymalny zestaw nieusuniętych krawędzi na pewno nie będzie zawierać cyklu. Gdyby były tylko dwa wyróżnione wierzchołki,  i   to nieusunięte krawędzie tworzyłyby najkrótszą ścieżkę z   do  W przypadku trzech wyróżnionych wierzchołków od ścieżki z   do  w pewnym miejscu odchodziłaby jeszcze ścieżka do  Po chwili namysłu dochodzimy do wniosku, że w przypadku czterech wyróżnionych wierzchołków nieusunięte krawędzie powinny tworzyć kształt taki jak na poniższym rysunku. Wyróżnione wierzchołki są tutaj połączone ścieżkami z pewnymi dwoma wierzchołkami  i  (nazwijmy je wierzchołkami centralnymi), które również są połączone ścieżką. Bez straty ogólności wierzchołek  i pewien inny wierzchołek  dla  są połączone z   pozostałe dwa są połączone z   Rysunek obejmuje również przypadki, gdy niektóre wierzchołki pokrywają się (np.  lub ) – w takich sytuacjach odpowiednie ścieżki mają zerową długość.

Jeśli przez  oznaczymy długość najkrótszej ścieżki pomiędzy wierzchołkami  i   to koszt powyższego rozwiązania wynosi

Parę wierzchołków centralnych  i   możemy wybrać na  sposobów, zaś wierzchołek  na trzy sposoby. Jednak złożoność czasowa algorytmu jest zdominowana przez obliczenie tablicy  które wykonujemy w czasie  za pomocą  wywołań algorytmu Dijkstry.

Zadanie można rozwiązać szybciej. Ustalmy  Niech graf  powstaje przez dodanie do grafu  dodatkowych wierzchołków  i dodatkowych krawędzi: wierzchołek  łączymy z każdym wierzchołkiem  krawędzią o wadze  zaś wierzchołek  łączymy z każdym  krawędzią o wadze

Zauważmy, że ścieżka  w grafie  odpowiada rozwiązaniu, w którym jako wierzchołki centralne wybieramy  i   koszt takiego rozwiązania jest równy długości tej ścieżki. Tak więc, aby rozwiązać zadanie, wystarczy dla każdego  znaleźć najkrótszą ścieżkę z   do  w grafie

Do konstrukcji grafu  musimy wyznaczyć wartości  dla  i   Ostatecznie nasze rozwiązanie wymaga siedmiu wywołań algorytmu Dijkstry (czterech w grafie  do obliczenia  i po jednym w grafie  dla każdego wyboru ). Graf  ma  wierzchołków i   krawędzi, więc koszt algorytmu Dijkstry jest w nim taki sam jak w grafie  Zatem rozwiązanie działa w czasie