V tomto případě už mohou být hrany grafu ohodnoceny čímkoliv, tedy i zápornými čísly. Záporná ohodnocení hran moc neodpovídají délkám hran. Ale ohodnocení si můžeme představit i jako cenu, kterou musíme zaplatit za průchod hranou. Záporná cena znamená, že naopak někdo zaplatí nám.

Pokud jsou hrany ohodnoceny i zápornými čísly, tak nemůžeme použít Dijkstrův algoritmus. Je to z toho důvodu, že nejkratší cesta může vést nejdříve do vrcholu, který je dál, a pak se vrátit po záporné hraně.

Ba co hůř, graf může obsahovat záporné cykly. Průchodem po záporném cyklu vyděláme. Je výhodné po něm procházet pořád dokola a postupně snižovat aktuální cenu cesty. Po nekonečně mnoha průchodech ji snížíme až na mínus nekonečno (nekonečně vyděláme). Pokud graf obsahuje záporný cyklus, tak nejlevnější řešení neexistuje. Na druhou stranu nejkratší cesta zcela jistě existuje, protože v konečném grafu je jen konečně mnoho cest. Taková cesta ale nemusí být nejlevnějším řešením naší úlohy. V případě záporných cyklů nemůžeme použít ani Floyd-Warshallův algoritmus, protože by nám mohl vydat nesprávnou odpověď (nenašel by cestu, ale tah, který ani nebude optimální).