A Bellman-Ford algoritmust miért kell csúcsszámszor végrehajtani?

Nem tudom, hogy hogyan tanultátok az algoritmust, de ezek szerint nem értetted meg, hogy mi történik.

Tehát tegyük fel, hogy adva van egy s csúcs, és az s-ből keresel egy legolcsóbb utat t-be (vagy az összes v csúcsba, hiszen az algoritmus mindegyikre megadja a választ).

Az i-edik fázisban (fázis = amikor egyszer végigmész az éleken) azt számolod ki minden v csúcsra, hogy a max i élű sv-séták közül melyik a legolcsóbb. Értelemszerűen minél több élet engedsz meg, annál több lehetséges séta közül kell venni a minimumot, tehát simán lehet, hogy az i+1-edik fázisban már jobbat kapsz.

Azért kell csúcsszámszor csinálni ezt, mert ha konzervatív élsúlyozás volt, akkor az algoritmus addigra már megtalálja a legolcsóbb utakat mindenhova, ha meg volt negatív kör, akkor addigra biztosan talál egyet.