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 printSolution(distance, points)
    for i=1:nodes
        //disp(string(i) + " " + string(distance(i)));
        mprintf("Node : %d\n", i);
        mprintf("Distance from start : %d\n", distance(1, i));
        mprintf("Path : ");
        printPath(points, i);
        disp("");
    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)
    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;
            end
        end
    end
    printSolution(distance, points);
    disp(points);
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 : ");

dijkstra(graph, startNode);