De ce contează?
Imaginează-ți că ai în mână o hartă a unui oraș. O întrebare e: „pot ajunge pe jos în toate cartierele, sau unele sunt izolate?". Cu totul altă întrebare e: „care e cel mai ieftin traseu cu autobuzul din Gară până în Piață?". Și mai e una: „vreau afișat, la intrarea în autogară, prețul minim între ORICARE două stații". Prima vrea doar să vizitezi tot; a doua cântărește costuri dintr-un singur punct de plecare; a treia cere un întreg tabel de prețuri. Dacă le confunzi, alegi unealta greșită — pornești să „vizitezi tot" când de fapt trebuia să compari prețuri.
Ideea-cheie
Toate algoritmele din acest capitol „umblă" prin graf — și de aici vine confuzia. Dar ele răspund la întrebări diferite. Parcurgerea (DFS/BFS) răspunde la „CE noduri pot atinge și în ce ordine le explorez". Drumul minim răspunde la „CARE e cel mai ieftin traseu de la A la B". Faptul că ambele se plimbă prin noduri și muchii nu le face același lucru — la fel cum „a vizita tot orașul" și „a găsi cel mai scurt drum" sunt două sarcini diferite, chiar dacă amândouă presupun să mergi pe străzi.
„POT ajunge?" și „CÂT mă costă?" sunt întrebări diferite, chiar dacă ambele umblă prin graf. Iar zona în care ele se suprapun e una singură: pe graf NEponderat, BFS dă și drumul minim — dar DOAR pentru că acolo toate muchiile costă la fel, deci „cel mai puține muchii" înseamnă automat „cel mai mic cost". În clipa în care muchiile au ponderi diferite, suprapunerea dispare.