global nodes;

function printPath(points, i)
    if points(1, i) ~= -1 then
        printPath(points, points(1, i));
        //disp(string(i) + " ");
        mprintf("%d ", i);
    end
endfunction

function result=findMin(distance, visited)
    min = 10000, minIndex = 0;
    for i=1:nodes
        if visited(1, i) == 0 & distance(1, i) <= min then
            minIndex = i;
            min = distance(1, i);       
        end
    end
    result = minIndex;
endfunction

function dijkstra(graph, start, target)
    distance = 10000*ones(1, nodes);
    points = zeros(1, nodes);
    visited = zeros(1, nodes);
    distance(1, start) = 0;
    points(1, start) = -1;
    for i=1:nodes-1 
        min = findMin(distance, visited);
        visited(1, min) = 1;
        for j=1:nodes
            if visited(1, j) == 0 & graph(min, j) > 0 & distance(1, min) ~= 10000 & distance(1, min)+graph(min, j) < distance(1, j) then
                distance(1, j) = distance(1, min) + graph(min, j);
                points(1, j) = min;
                if j == target
                    mprintf("Distance from start : %d\n", distance(1, j));
                    mprintf("%d ", start);
                    printPath(points, target);
                    return;
                end
            end
        end
    end
endfunction
   
function [from, to, weight]=split(data, flag)
    splitted = evstr(strsplit(data, " "));
    from = splitted(1, 1);
    to = splitted(2, 1);
    if flag == 1 then
        weight = 1; 
    else
        weight = splitted(3, 1);
    end
endfunction

nodes = input("How many nodes ? ");
graph = zeros(nodes, nodes);
flag = input("Does all edges have the same weight (1.yes, 2. no)? ");
edges = input("How many edges ? ");
if flag == 1 then
    disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
else
    disp("Enter " + string(edges) + " edges (from-to-weight) separated by a white space:");
end
for i=1:edges
    in = input("", "string");
    [from, to, weight] = split(in, flag);
    graph(from, to) = weight;
    graph(to, from) = weight;   
end
    
startNode = input("Enter initial node : ");
targetNode = input("Enter target node : ");

dijkstra(graph, startNode, targetNode);