Dijkstra-Recursive-Algorithm/ShortestPath_Matlab.m at main · SimoneRemoli/Dijkstra-Recursive-Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function Edsger_Wybe_Dijkstra()
  %Simone Remoli Calcolo_Percorsi_Minimi

  %Per ciscuna matrice degli esercizi precedenti, calcolare il percorso minimo
  %a partire dal nodo A a tutti gli altri nodi
  fprintf("Benvenuto! Edsger Wybe Dijkstra-Calcolo Percorsi Minimi !  \n ")
  X = input("Di quale matrice si desidera vedere il percorso minimo ? :");
 switch (X)
  case 1
    mat = [0,1,0,0,0;1,0,1,0,0;0,1,0,1,0;0,0,1,0,1;0,0,0,1,0]
  case 2
    mat = [0,1,1,1,1,1;1,0,0,0,0,0;1,0,0,0,0,0;1,0,0,0,0,0;1,0,0,0,0,0;1,0,0,0,0,0]
  case 3
    mat = [0,1,1,0,0,0,0,0,0;1,0,0,0,0,0,1,1,1;1,0,0,1,1,1,0,0,0;0,0,1,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0;0,0,1,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0;0,1,0,0,0,0,0,0,0]
endswitch

  for i=1:size(mat)
    cost(i)=inf;
    conosciuti(i)=0;
  end;

  cost(1)=0;
  conosciuti(1)=1;
  nodo_attuale = 1;
 for matrix_type=1:size(mat) %ciclo (inizio)---------------------------------------
    for i=1:size(mat)
      if (mat(i,nodo_attuale)~=0&&((mat(i,nodo_attuale)+cost(nodo_attuale))<cost(i)))
        cost(i) = (cost(nodo_attuale)+mat(i,nodo_attuale));
      end;
    end;
  min = Inf;
    for i=1:size(mat)
      if((cost(i)<min)&&(conosciuti(i)==0))%se il valore iesimo di cost è minore del minimo e non è stato visitato
        min = cost(i); %trovo il minimo
        c = i; %c = indice del minimo
      end;
    end;
    conosciuti(c)=1;
    nodo_attuale = c;
end; %ciclo (fine)-------------------------------------------------------------------
conosciuti
cost


%Output

%   0   1   1   0   0   0   0   0   0
%   1   0   0   0   0   0   1   1   1
%   1   0   0   1   1   1   0   0   0
%   0   0   1   0   0   0   0   0   0         <---- matrice di adiacenza
%   0   0   1   0   0   0   0   0   0
%   0   0   1   0   0   0   0   0   0
%   0   1   0   0   0   0   0   0   0
%   0   1   0   0   0   0   0   0   0
%   0   1   0   0   0   0   0   0   0

%conosciuti =

 %  1   1   1   1   1   1   1   1   1      <--- tutto il vettore è settato a true

%cost =

 %  0   1   1   2   2   2   2   2   2       <---- distanze