Najdôležitejšie a jediné netriviálne tvrdenie našeho riešenia hovorí, že z nespracovaných vrchlov môžeme zobrať vrchol s najkratšou cestou a prehlásiť ho za spracovaný. A že táto dĺžka je skutočne dĺžkou najkratšej cesty, ktorá do neho vedie.
Majme teda nejaké spracované vrcholy a potom nespracované vrcholy,
pre ktoré poznáme dĺžku najkratšej cesty vedúcej z $a$
do nich, ktorá vedie iba cez spracované vrcholy.
Nech $x$ je nespracovaný vrchol,
do ktorého vedie najkratšia takáto cesta a jej dĺžku si označme D[x].
My tvrdíme, že táto cesta je skutočne najktrašia možná z vrchola $a$ do vrchola $x$.
Čo by muselo platiť, aby to nebola pravda?
Musela by existovať taká cesta z $a$ do $x$,
ktorá je kratšia a vedie cez aspoň jeden ešte nespracovaný vrchol
(lebo z tých, čo vedú cez spracované už máme najmenšiu možnosť).
Takže najskôr pôjde táto cesta z vrchola $a$ po spracovaných vrchloch
a potom prejde do nespracovaných a nejakým spôsobom príde až do vrchola $x$.
Avšak, už tá prvá časť má dĺžku aspoň D[x].
Nech $y$ je prvý nespracovaný vrchol, ktorý takáto cesta navštívi.
Je jasné, že platí D[x]≤D[y], pretože D[x] bola najkratšia z ciest
do nespracovaného vrchola.
A ak pôjdeme medzi vrcholmi $y$ a $x$, k tejto dĺžke iba pridáme,
pretože všetky naše hrany majú nezápornú dĺžku.
Preto je hodnota D[x] naozaj správna.
Toto zároveň ukazuje dôvod, prečo sme vyžadovali nezápornosť hrán. Ak by sa totiž v našom grafe nachádzali záporné hrany, táto podmienka by neplatila a celý Dijkstrov algoritmus by nebol správny. A ak vás napadne, že stačí nájsť najviac zápornú hranu a potom ku každej hrane pripočítať túto hodnotu, čím budú všetky hrany nezáporné, tak to nerobte. Nebude to totiž fungovať, skúste si premyslieť prečo. Ak chcete hľadať najkratšie cesty v grafoch so zápornými hranami, musíte použiť robustnejšie algoritmy, akým je napríklad Floyd-Warshallov algoritmus.