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