• Înțelegerea ideii de cost și de drum minim într-un graf
• Prezentarea algoritmilor care calculează drumul de cost minim
• Înțelegerea aplicațiilor practice prezente în:
  • găsirea drumului minim între 2 locații (ex: GPS)
  • rutarea în cazul rețelelor de calculatoare (ex: protocolul RIP)

La fel ca la arbori de acoperire, presupunem că fiecare muchie are un cost de parcurgere.

Într-un graf, orice drum este definit de o succesiune de muchii (cu proprietatea că, pentru oricare două muchii consecutive din succesiune, nodul destinaţie/de sosire al primei muchii este acelaşi cu nodul sursa/de plecare al celei de-a doua muchii).

Costul unui drum va fi definit ca suma costurilor muchiilor ce compun acel drum.

Fie un nod sursă(S) şi un nod destinaţie(D). Pot exista mai multe drumuri de la S la D(drumuri care au S = primul nod, D = ultimul nod), iar drumul de cost minim de la S la D va fi cel mai ieftin(cu costul cel mai mic) dintre acestea.

Următorii algoritmi caută drumurile de cost minim de la un singur nod(sursă) la toate celelalte noduri. Rezultatul acestor algoritmi este un arbore cu drumuri de cost minim, unde:

• nodul sursă(S) este rădăcina arborelui;
• toate nodurile din graf sunt în arbore;
• pentru orice nod destinaţie(D), costul drumului din arbore de la rădăcina S la D este drum de cost minim(de la S la D) în graf.

1. Algoritmul lui Dijkstra
2. Algoritmul lui Bellman Ford
3. Algoritmul lui Floyd-Warshall
4. Protocoale de rutare
5. Link extern