Algoritmul Prim

Este foarte util să se aibă în vedere asemănarea deosebită cu algoritmul Dijkstra (cu toate că fac lucruri diferite). În cod practic este vorba de o singură valoare care la Dijkstra se adună iar la Prim nu. Acest detaliu de implementare va fi subliniat la secțiunea dedicată algoritmului Dijkstra.

La un moment dat în cadrul algoritmului Prim avem construit un subarbore al arborelui parțial de cost minim iar pentru fiecare nod care nu face încă parte din el cunoaștem distanța minimă la unul dintre nodurile din subarbore.

Ceea ce avem de făcut la un pas este să selectăm nodul cu valoarea minimă a acestei distanțe și apoi să actualizăm distanțele minime la celelalte noduri încă nealese luând în calcul și muchii cu o extremitate în nodul tocmai ales.