SHARE
TWEET

Dijkstra

Infernale Sep 13th, 2019 197 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. global nodes;
  2.  
  3. function printPath(points, i)
  4.     if points(1, i) ~= -1 then
  5.         printPath(points, points(1, i));
  6.         //disp(string(i) + " ");
  7.         mprintf("%d ", i);
  8.     end
  9. endfunction
  10.  
  11. function printSolution(distance, points)
  12.     for i=1:nodes
  13.         //disp(string(i) + " " + string(distance(i)));
  14.         mprintf("Node : %d\n", i);
  15.         mprintf("Distance from start : %d\n", distance(1, i));
  16.         mprintf("Path : ");
  17.         printPath(points, i);
  18.         disp("");
  19.     end
  20. endfunction
  21.  
  22. function result=findMin(distance, visited)
  23.     min = 10000, minIndex = 0;
  24.     for i=1:nodes
  25.         if visited(1, i) == 0 & distance(1, i) <= min then
  26.             minIndex = i;
  27.             min = distance(1, i);      
  28.         end
  29.     end
  30.     result = minIndex;
  31. endfunction
  32.  
  33. function dijkstra(graph, start)
  34.     distance = 10000*ones(1, nodes);
  35.     points = zeros(1, nodes);
  36.     visited = zeros(1, nodes);
  37.     distance(1, start) = 0;
  38.     points(1, start) = -1;
  39.     for i=1:nodes-1
  40.         min = findMin(distance, visited);
  41.         visited(1, min) = 1;
  42.         for j=1:nodes
  43.             if visited(1, j) == 0 & graph(min, j) > 0 & distance(1, min) ~= 10000 & distance(1, min)+graph(min, j) < distance(1, j) then
  44.                 distance(1, j) = distance(1, min) + graph(min, j);
  45.                 points(1, j) = min;
  46.             end
  47.         end
  48.     end
  49.     printSolution(distance, points);
  50.     disp(points);
  51. endfunction
  52.    
  53. function [from, to, weight]=split(data, flag)
  54.     splitted = evstr(strsplit(data, " "));
  55.     from = splitted(1, 1);
  56.     to = splitted(2, 1);
  57.     if flag == 1 then
  58.         weight = 1;
  59.     else
  60.         weight = splitted(3, 1);
  61.     end
  62. endfunction
  63.  
  64. nodes = input("How many nodes ? ");
  65. graph = zeros(nodes, nodes);
  66. flag = input("Does all edges have the same weight (1.yes, 2. no)? ");
  67. edges = input("How many edges ? ");
  68. if flag == 1 then
  69.     disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
  70. else
  71.     disp("Enter " + string(edges) + " edges (from-to-weight) separated by a white space:");
  72. end
  73. for i=1:edges
  74.     in = input("", "string");
  75.     [from, to, weight] = split(in, flag);
  76.     graph(from, to) = weight;
  77.     graph(to, from) = weight;  
  78. end
  79.    
  80. startNode = input("Enter initial node : ");
  81.  
  82. dijkstra(graph, startNode);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top