Problém nejdelší cesty a jeho aplikace v železniční dopravě

Abstract

Práce se bude zabývat problémem nalezení jednoduché cesty maximální délky v daném grafu. Cesta se nazývá jednoduchá, pokud nemá žádné opakované vrcholy. Délka cesty může být buď měřena jejím počtem hran, nebo (ve vážených grafech) součtem vah jejích hran. Na rozdíl od problému s nejkratší cestou, kterou lze vyřešit v polynomiálním čase v grafech bez cyklů se zápornou váhou, je problém s nejdelší cestou NP-těžký. Tento problém lze aplikovat např. v dopravních problémech.