Hledání nejkratších cest

Problém nalezení nejkratší cesty mezi 2 vrcholy pro graf ohodnocený obecnými (tedy i zápornými) délkami je NP-úplný, proto pro něj není známý efektivní algoritmus

Pro některá speciální ohodnocení existují

• Dijkstra - předpokládá kladné délky hran
• Bellman-Ford - připouští záporné délky, ale předpokládá neexistenci záporných cyklů

Ve skutečnosti tedy není znám efektivní algoritmus na hledání nejkratších cest

Toto jsou příklady algoritmů na hledání nejkratších sledů