Do wyznaczania najkrótszej ścieżki pomiędzy dwoma wierzchołkami służy algorytm Dijkstry.
Jeżeli rozpatrywany graf G nie jest półeulerowski, to znaczy, że posiada przynajmniej 4 wierzchołki nieparzystego stopnia. Z wszystkich wierzchołków nieparzystego stopnia grafu G należy utworzyć graf H, w taki sposób aby graf H był grafem pełnym z wagami na krawędziach odpowiadającymi najmniejszej ścieżce pomiędzy wierzchołkami w grafie G. W grafie H należy znaleźć minimalne skojarzenie doskonałe i uzupełnić o nie graf G. Graf G jest teraz multigrafem eulerowskim, w którym rozwiązaniem problemu chińskiego listonosza jest cykl Eulera.
Przypisy
Linki zewnętrzne Wykład MiNI PW o problemie chińskiego listonosza [dostęp 2025-12-20].
C