function [L, ant] = dijkstra(D, costos, a)
// Ejecuta el algoritmo de Dijkstra 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

// Calcula grados salientes de vértices y N+
// La fila i-esima de N+ contiene los vértices que salen de i en D
// La fila i-esima de costos+ contiene los costos de ir de i a los de N+(i)
grados = zeros(1, nodos);
Nmas = zeros(nodos, nodos);
costosmas = zeros(nodos, nodos);
for e = 1:arcos
    v = D(1,e);
    w = D(2,e);
    grados(v) = grados(v) + 1;
    Nmas(v,grados(v)) = w;
    costosmas(v,grados(v)) = costos(e);
end

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

// Los conjuntos V1 y V2 se representan mediante sus vectores característicos
V1 = zeros(1, nodos);
V2 = zeros(1, nodos);
V1(a) = 1;
cardinal_V1 = 1;

// ITERACION
while cardinal_V1 > 0 do
    // Paso 1
    v = -1;
    Lv = 999999; 
    for u = 1:nodos
        if V1(u) == 1 & L(u) < Lv then
            v = u;
            Lv = L(u);
        end
    end
    
    mprintf('Iteracion con v = %1.0f, L(v) = %1.0f\n', v, Lv)

    // Paso 2
    for d = 1:grados(v)
        w = Nmas(v,d);
        if V2(w) == 0 then
            cvw = costosmas(v,d);
            mprintf('Probando con w = %1.0f: L(w) = %1.0f, c_vw = %1.0f\n', w, L(w), cvw)
            if Lv + cvw < L(w) then
                L(w) = Lv + cvw;
                ant(w) = v;
                if V1(w) == 0 then
                    V1(w) = 1;
                    cardinal_V1 = cardinal_V1 + 1;
                end
                mprintf('Se re-etiqueta el vértice %1.0f con (%1.0f, %1.0f)\n', w, L(w), ant(w))
            end
        end
    end
    
    // Paso 3
    V1(v) = 0;
    cardinal_V1 = cardinal_V1 - 1;
    V2(v) = 1;
end

endfunction
