De ce contează?
Pornești GPS-ul și ceri ruta cea mai ieftină, nu cea cu cele mai puține străzi: autostrada cu taxă te duce direct, dar trei drumuri județene gratuite te costă de trei ori mai puțin. Pe o hartă cu prețuri, „cel mai scurt drum" nu se numără în străzi, ci în lei. Lecția asta îți arată ce înseamnă exact „drum de cost minim", de ce unealta ta veche — BFS — dă aici răspunsuri greșite, și cum alegi între Dijkstra, Bellman-Ford și Roy-Floyd, uneltele pe care le ai deja în trusă.
Intuiția
„Drum de cost minim" înseamnă: dintre toate căile de la un nod la altul, o vrei pe cea cu suma costurilor cea mai mică. Toate cele patru unelte rezolvă fix această problemă, dar fiecare presupune ceva despre graf. Dacă alegi unealta greșită, primești fie un răspuns greșit, fie un TLE. Trucul nu e să le memorezi, ci să legi fiecare unealtă de o proprietate a grafului: ponderat sau nu, costuri negative sau nu, o sursă sau toate perechile.
Mai puține muchii nu înseamnă cost mai mic: o singură muchie de cost 10
pierde în fața a trei muchii de cost 1+1+1 = 3. Într-un graf ponderat,
„cel mai scurt" = suma costurilor minimă, indiferent câte muchii are drumul.