function [L, ant] = ford_bellman(D, costos, a)
// Ejecuta el algoritmo de Ford-Bellman sobre un digrafo (ver Práctica 2)
// Entrada:
//  D = vector de 2 filas con los extremos de los arcos del digrafo
//  costos = vector de costos (cada componente es para una arista)
//  a = vértice inicial
// Salida:
//  L = vector con los tamaños del camino desde a hasta el vértice en cuestión
//  ant = vector con los vértices predecesores en el camino


nodos = max(D); // Obtiene cantidad de vértices
[zzz, arcos] = size(D); // Obtiene cantidad de arcos

// INICIALIZACION
for v = 1:nodos
    L(v) = 999999;
    ant(v) = -1;
end
L(a) = 0;

i = 0;
hubo_actualizacion = %t;

// ITERACION
while i < nodos & hubo_actualizacion do
    // Paso 1
    i = i + 1;
    hubo_actualizacion = %f;

    mprintf('Iteracion %1.0f\n', i)

    // Paso 2
    for e = 1:arcos
        v = D(1,e);
        w = D(2,e);
        mprintf('Probando arco (%1.0f, %1.0f): L(v) = %1.0f, L(w) = %1.0f, c_vw = %1.0f\n', v, w, L(v), L(w), costos(e))
        if L(v) + costos(e) < L(w) then
            L(w) = L(v) + costos(e);
            ant(w) = v;
            hubo_actualizacion = %t;
            mprintf('Se re-etiqueta el vértice %1.0f con (%1.0f, %1.0f)\n', w, L(w), ant(w))
        end
    end
end

if (i == nodos) then
    disp('Ciclo con costo negativo!')
end

endfunction
