• API
• FAQ
• Tools
• Archive
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.
Top