Rys. 1 Optymalne rozwiązanie dla powyższego grafu to  i  Ścieżki przechodzą łącznie przez 6 wierzchołków.

Po przetłumaczeniu historyjki o sieci komputerowej na język teorii grafów brzmi ono następująco. Dany jest skierowany graf  mający  wierzchołków, z których wyróżniamy początkowy   i końcowy   Chcemy znaleźć w grafie   dwie skierowane ścieżki  i  (pierwszą z   do   a drugą z   do  ) tak, by łączna liczba wierzchołków, przez które przechodzą te ścieżki, była jak najmniejsza (Rys. 1).

W rozwiązaniu będziemy konstruowali obie ścieżki, poruszając się od wierzchołka   dla pierwszej z nich zgodnie ze skierowaniem krawędzi, a dla drugiej – przeciwnie. Zdefiniujmy w tym celu ważony graf skierowany  w którym z wierzchołka  wychodzą krawędzie:

(1)

(1) do  o wadze  jeśli

(2)

(2) do  o wadze  jeśli

(3)

(3) do  o wadze  jeśli w   istnieje skierowana ścieżka z   do   i najkrótsza taka ścieżka zawiera  krawędzi.

Krawędzie (1) i (2) w   odpowiadają przesuwaniu się ścieżką   w   zgodnie ze skierowaniem krawędzi i ścieżką   przeciwnie do skierowania krawędzi. Natomiast krawędź (3) w   odpowiada przesunięciu się obiema ścieżkami po tych samych krawędziach w   Łatwo się więc przekonać, że jeżeli w   istnieje ścieżka z   do   o wadze   to oznacza, że w   istnieją dwie ścieżki, pierwsza z   do   i druga z   do   takie że sumaryczna liczba wierzchołków, przez jakie przechodzą (nie licząc  i  ), jest równa co najwyżej   W szczególności, ścieżka w   z   do   o wadze   implikuje istnienie rozwiązania zadania o koszcie 

Pozostaje nam wykazać, że jeśli w optymalnym rozwiązaniu ścieżki  i   przechodzą przez  wierzchołków, to w grafie   istnieje ścieżka z   do   o wadze   Niech  będzie listą wierzchołków wspólnych dla obu ścieżek w kolejności, w jakiej te wierzchołki występują na ścieżce   Powiemy, że wierzchołki  tworzą blok, jeśli są one odwiedzane w tej kolejności również przez ścieżkę  (oznaczymy to przez ). Zauważmy, że z optymalności ścieżek  i   wynika, że na każdej ze ścieżek między wierzchołkami należącymi do tego samego bloku nie występują wierzchołki spoza   Podobny argument dowodzi tego, że jeśli ścieżka   odwiedza wierzchołek   jako najbliższy wierzchołek z   po wierzchołku   to  Jeśli więc  podzielimy na maksymalne bloki w kolejności ich odwiedzania przez ścieżkę   to ścieżka   będzie je odwiedzać w odwrotnej kolejności. Ponadto pierwszy i ostatni blok podziału będą to odpowiednio  i 

Rys. 2

Pokażemy (Rys. 2), że dla kolejnych dwóch bloków  i   tego podziału istnieje ścieżka w grafie   z   do   o wadze  gdzie    to odpowiednio liczby wierzchołków spoza   odwiedzanych przez ścieżkę   od   do   oraz przez ścieżkę   od   do   natomiast  to rozmiar bloku  Istotnie, z   do   przechodzimy  krawędziami (1), następnie z   do   przechodzimy  krawędziami (2) o łącznej wadze  i ostatecznie (jeśli ) używamy krawędzi (3) o wadze  aby dostać się z   do   W ten sposób konstruujemy ścieżkę w   która odwiedza wszystkie bloki i ma wagę równą 

Tak więc dowiedliśmy, że aby znaleźć rozwiązanie, wystarczy, że wyznaczymy najlżejszą ścieżkę z   do   w grafie   Możemy to zrobić algorytmem Dijkstry, na bieżąco konstruując graf   Za każdym razem, gdy z kolejki priorytetowej wyciągamy wierzchołek  przechodzimy po liście sąsiedztwa  w   i relaksujemy krawędzie (1), następnie przechodzimy po liście sąsiedztwa   w grafie transponowanym   i relaksujemy krawędzie (2); w końcu sprawdzamy, czy  i jeśli tak, relaksujemy krawędź (3).

Graf  ma  wierzchołków. Każdy z nich jest początkiem  krawędzi (1) i (2) i co najwyżej jednej krawędzi (3), zatem w   mamy  krawędzi. Ponadto uaktualnienie wagi wierzchołka podczas relaksacji będzie wykonywane tylko  razy, gdyż krawędzie wchodzące do każdego wierzchołka w   mają co najwyżej trzy różne wagi. Zatem złożoność czasowa rozwiązania wyniesie  Tyle też będzie trwało obliczenie długości najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w   jeśli użyjemy do tego algorytmu Floyda–Warshalla.