Problémy existence nejdelší cesty a nejkratší cesty jsou NP-úplné grafové úlohy. Pokud bychom pouze věděli (důkaz), že je problém nejdelší cesty NP-úplný, ale o problému nejkratší cesty tuto informaci neměli, tak tento převod dokazuje NP-úplnost úlohy nejkratší cesty (dále je ještě zapotřebí ukázat, že lze ověřit ANO-instanci v polynomiálním čase – stačí posčítat délky jednotlivých hran cesty).

V případě, že je graf acyklický (nebo neobsahuje cyklus záporné délky pro nejkratší cesty a cyklus kladné délky pro nejdelší cesty), tak jsou oba problémy řešitelné v polynomiálním čase použitím Floyd-Warshallova algoritmu.

Nejdelší cesta

Rozhodovací problém nejdelší cesty se ptá, zda-li daný graf obsahuje (acyklickou) cestu délky alespoň k.

Nejkratší cesta

Rozhodovací problém nejkratší cesty se ptá, zda-li daný graf obsahuje (acyklickou) cestu délky nejvýše k.

Převod

Pro převod úlohy stačí v grafu otočit znaménka cen všech hran a čísla k. Protože součet cen nejdelší cesty je v daném grafu maximální, tak je grafu takto upraveném minimální – což odpovídá problému hledání nejkratší cesty (a analogicky naopak).