SHARE
TWEET

Dijkstra V1.1

Infernale Oct 26th, 2019 134 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 result=findMin(distance, visited)
  12.     min = 10000, minIndex = 0;
  13.     for i=1:nodes
  14.         if visited(1, i) == 0 & distance(1, i) <= min then
  15.             minIndex = i;
  16.             min = distance(1, i);      
  17.         end
  18.     end
  19.     result = minIndex;
  20. endfunction
  21.  
  22. function dijkstra(graph, start, target)
  23.     distance = 10000*ones(1, nodes);
  24.     points = zeros(1, nodes);
  25.     visited = zeros(1, nodes);
  26.     distance(1, start) = 0;
  27.     points(1, start) = -1;
  28.     for i=1:nodes-1
  29.         min = findMin(distance, visited);
  30.         visited(1, min) = 1;
  31.         for j=1:nodes
  32.             if visited(1, j) == 0 & graph(min, j) > 0 & distance(1, min) ~= 10000 & distance(1, min)+graph(min, j) < distance(1, j) then
  33.                 distance(1, j) = distance(1, min) + graph(min, j);
  34.                 points(1, j) = min;
  35.                 if j == target
  36.                     mprintf("Distance from start : %d\n", distance(1, j));
  37.                     mprintf("%d ", start);
  38.                     printPath(points, target);
  39.                     return;
  40.                 end
  41.             end
  42.         end
  43.     end
  44. endfunction
  45.    
  46. function [from, to, weight]=split(data, flag)
  47.     splitted = evstr(strsplit(data, " "));
  48.     from = splitted(1, 1);
  49.     to = splitted(2, 1);
  50.     if flag == 1 then
  51.         weight = 1;
  52.     else
  53.         weight = splitted(3, 1);
  54.     end
  55. endfunction
  56.  
  57. nodes = input("How many nodes ? ");
  58. graph = zeros(nodes, nodes);
  59. flag = input("Does all edges have the same weight (1.yes, 2. no)? ");
  60. edges = input("How many edges ? ");
  61. if flag == 1 then
  62.     disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
  63. else
  64.     disp("Enter " + string(edges) + " edges (from-to-weight) separated by a white space:");
  65. end
  66. for i=1:edges
  67.     in = input("", "string");
  68.     [from, to, weight] = split(in, flag);
  69.     graph(from, to) = weight;
  70.     graph(to, from) = weight;  
  71. end
  72.    
  73. startNode = input("Enter initial node : ");
  74. targetNode = input("Enter target node : ");
  75.  
  76. dijkstra(graph, startNode, targetNode);
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