Una din problemele care apar foarte des în practică este găsirea drumului optim între două noduri ale unui graf.

Formalizarea problemei drumului optim este următoarea:

“Fiind dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)”.

Valoarea unui drum este dată de suma valorilor arcelor care îl compun. Pentru problema drumului optim s-au elaborat mai multe categorii de algoritmi, după cum urmează:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell)
Algoritmi prin ajustări succesive (Ford)
Algoritmi prin inducţie (Dantzig)
Algoritmi prin ordonare prealabilă a vârfurilor grafului
Algoritmi prin extindere selectivă (Dijkstra)