4.3.3. Problemas de caminos mínimos.
Un camino especial del origen a otro nodo cualquiera es un camino que sólo pasa por nodos ya escogidos.
Supongamos que el nodo origen es el 1.
En un array D[2, ..., N] se guarda la longitud del camino especial más corto a cada vértice. Cuando todos los nodos estén en S, todos los caminos son especiales y D contiene las distancias mínimas al origen.
En otro array P[2, ..., N] se almacena el camino por el que pasa cada nodo v. El camino de 1 a v pasa por P[v].
Inicialmente D contendrá los caminos directos de 1 a los restantes nodos, es decir C[1, x]. Si no existe la arista (1, x) el costo será ?. P contendrá el valor 1 (el camino es directo). S contendrá sólo el nodo 1.
Buscar el nodo v de C=V-S con mínimo valor de D. Añadir v a S. Para el resto de nodos comprobar si el camino al origen es más corto pasando por el nodo v.
if D[v]+C[v, w] < D[w] then begin
D[w]:= D[v] + C[v, w];
P[w]:= v;
end;