Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

En la transparencia 55 de programación dinámica quedó como ejercicio el cálculo de los nodos de las secuencias que componen los caminos mínimos desde cualquier nodo i a cualquier nodo j. Hay varias formas de resolverlo. Una muy sencilla consiste en guardar una matriz adicional C[v,w] en la que se almacene un nodo u que esté en el camino mínimo de v a w. Para ello, en el interior de los tres bucles del algoritmo, hay que modificar la instrucción condicional añadiendo la actualización de esa matriz C:

  si D[i,k]+D[k,j]<D[i,j] entonces
    D[i,j]:=D[i,k]+D[k,j];
    C[i,j]:=k
  fsi

La matriz se ha debido inicializar al principio del algoritmo (por ejemplo con valores nulos). El algoritmo para el cálculo del camino mínimo de i a j, usando la matriz C, queda como:

  procedimiento camino(ent i,j:vértice;
                       ent C:vector[vértice,vértice] de entero)
  variable k:vértice
  principio
    k:=C[i,j];
    si k≠0 entonces
      camino(i,k,C);
      escribir(k);
      camino(k,j,C)
    fsi
  fin

Comentarios