% Questo programma permette di risolvere il problema dei cammini minimi su un grafo
% tramite l'algoritmo di Dijkstra. Tale algoritmo, fissato un nodo iniziale, trova
% i cammini minimi da esso a ciascuno degli altri nodi. Il costo e' quadratico nel
% numero dei nodi del grafo.



%                     Commenti a cura di Beatrice Signorello



% Un grafo e' costituito da un insieme di punti (NODI) uniti da linee (LINK). Ne esistono
% vari tipi e possono rappresentare in modo schematico una grande quantita' di sistemi.
% Per esempio un grafo puo' rappresentare una mappa stradale dove i nodi corrispondono
% agli incroci ed i link alle strade. Tra le varie proprieta' di un grafo ricordiamo: 
% 1) la connettivita': se per ogni coppia di nodi esiste un percorso (PATH), 
% inteso come successione di link, che ci permette di arrivare da uno all'altro;
% 2) la completezza: se da ogni nodo ho un link che lo collega a ciascuno degli altri. 
% In questo tipo di grafo abbiamo n*(n-1) link. 
% Ad ogni grafo di n nodi possiamo associare una matrice n*n, detta matrice di ADIACENZA (A):
% e' una matrice i cui valori solo zero o uno; il suo generico elemento A(i,j) vale 1 se
% esiste un link dal nodo i al nodo j, altrimenti vale 0.
% Una classe importante di grafi e' quella dei grafi "PESATI". Per un grafo di questo tipo si ha
% la matrice dei "PESI" o delle "DISTANZE": e' utile se ci interessa conoscere, oltre ai 
% collegamenti, un'informazione specifica per ogni singolo collegamento. Chiaramente assegneremo
% un peso alla coppia (i,j) solo se esiste un link da i a j.


% Il problema dei cammini minimi su un grafo connesso e' quello di trovare un percorso da un nodo
% iniziale init ad uno finale fin la cui somma dei pesi sia minima, tra tutti i percorsi possibili
% da init a fin. Il numero di tali percorsi aumenta all'aumentare dei nodi e delle connessioni.
% Ad esempio, in un grafo completo abbiamo (n-1)! percorsi.

%   IDEA GENERALE DELL'ALGORITMO di Dijkstra:

% L'algoritmo e' composto da n-1 iterazioni in cui visita i nodi del grafo. Alla fine di ciascuna
% iterazione determina il percorso ottimale da init ad uno degli altri n-1 nodi. Se ci interessa
% solo il percorso fino a fin, interromperemo l'algoritmo all'iterazione in cui questo avviene.
% Completando tutte le n-1 iterazioni, avremo tutti i percorsi minimi da init a ciascuno degli
% altri n-1 nodi. Il costo in entrambi i casi sara' di ordine n^2.
% Alla fine di ciascuna iterazione, ciascun nodo ha associata un'etichetta: '0' se non e' stato
% ancora visitato, '1' se e' stato gia' visitato ma ancora non e' stato trovato il percorso
% ottimale da init ad esso, '2' se e' stato visitato ed e' stato trovato il percorso ottimale da
% init fino ad esso. Inoltre a ciascun nodo e' associato il percorso migliore trovato fino ad
% allora. Osservazione: le etichette ed i cammini migliori saranno mutabili nel corso
% dell'algoritmo. Pero', se l'etichetta assume il valore 2 alla fine di una iterazione, esso non
% cambiera' piu' alle iterazioni successive ed anche il percorso migliore rimarra' invariato.
% All'inizio inizializzo tutte le etichette a 0 esclusa quella del nodo init che metto a 2
% ed il relativo percorso (init,init), con costo totale minimo fittizio nullo.
% Supponiamo ora di aver finito una generica iterazione i, dove abbiamo assegnato il valore 2
% all'etichetta del nodo k_i, il cui percorso ottimale da init e' cosi' appena stato trovato.
% All'inizio della successiva iterazione, prolunghiamo il cammino ottimale di k_i aggiungendo
% uno degli s(k_i) link uscenti da esso, raggiungendo cosi' s(k_i) nodi. Esaminiamo ciascuno
% di questo s(k_i) nodi. Se e' la prima volta che esso viene raggiunto, assegneremo il valore
% 1 alla sua etichetta e memorizzeremo il cammino appena prolungato che lo raggiunge. Se invece
% la sua etichetta era gia' 1, cioe' era gia' stato raggiunto da un altro percorso, andremo
% a controllare se il peso totale (somma dei pesi) del nuovo percorso e' inferiore a quello
% del vecchio, che era il migliore fino a quel momento. In tal caso, sostituiremo il percorso
% vecchio con quello nuovo. A questo punto, consideriamo tutti i nodi che al momento hanno
% 1 come etichetta. Assegneremo 2 a quello il cui percorso migliore al momento e' piu' piccolo.
% Se ce n'e' piu' di uno, ne scegliamo uno di essi, come meglio crediamo. Abbiamo cosi' completato
% l'iterazione e possiamo passare alla seguente.


% IMPLEMENTAZIONE

clear
close all
n=8; % numero dei nodi
% Come esempio abbiamo scelto un grafo costituito da n punti equidistanti su una circonferenza.
% Ogni punto e' collegato solo ai suoi due primi vicini andando cosi' a formare un poligono regolare.
for i=1:n
  theta(i)=(i-1)*2*pi/n
end
% Usiamo un ciclo for per costruire il vettore theta che ha come i-esima componente l'angolo delle
% coordinate polari dell'i-esimo punto

x=[cos(theta);sin(theta)]
% matrice 2 x n che ha come colonne le coordinate x e y di ciascun punto del poligono regolare.

A=zeros(n,n);  % matrice di adiacenza momentaneamente costituita solo da zeri.
% La A ci dice quali sono i link. Per il nostro caso ci sono solo tra vertici adiacenti.
% Ricordiamo che i nostri punti sono considerati ordinati da 1 ad n. Tutti i punti hanno un
% vicino sinistro ed uno destro. Per i da 2 a n-1, essi sono i-1 ed i+1.
for i=2:n-1
  A(i,i-1)=1;
  A(i,i+1)=1;
end

% I vicini di 1 sono 2 ed n.
A(1,n)=1;
A(1,2)=1;

% I vicini di n sono 1 ed n-1.
A(n,1)=1;
A(n,n-1)=1;


% caso grafo completo 
% A=ones(n,n);
% for i=1:n
% A(i,i)=0;
% end

A
% Scriviamo sullo schermo la matrice di adiacenza A. Per la i-esima riga, essendo indicati con 1
% i due collegamenti del punto i-esimo avremo tutti zeri tranno due "uno": uno a sinistra e
% uno a destra dell'i-esima colonna. Questo per ogni riga a parte la prima e l'ultima. Notare
% che A in questo esempio e' una matrice CIRCOLANTE!!

dist=zeros(n,n); % MATRICE DELLE DISTANZE:la inizializziamo con tutti zeri 
figure
hold on
for i=1:n
  for j=1:n % Due cicli per controllare ogni coppia di punti
  if A(i,j) == 1 % Condizione necessaria affinche' ci sia un link tra i e j. Non avrebbe senso
% altrimenti calcolare la distanza.
  dist(i,j)=sqrt((x(1,i)-x(1,j))^2+(x(2,i)-x(2,j))^2); % Calcoliamo la distanza eucliea tra 
% i punti i e j con la nota formula, avendo ogni punto due componenti contenute nella matrice x
% che ha 2 righe (numero coordinate per ogni punto) ed n colonne (numero dei punti).
% x(1,i)-x(1,j) e' la differenza tra la prima coordinate dei punti i e j ed analogamente 
% x(2,i)-x(2,j) per la seconda coordinata.
  plot([x(1,i) x(1,j)],[x(2,i) x(2,j)]) % Disegnamo ogni volta un segmento tra i due punti di cui
% abbiamo appena calcolato la distanza. Queste operazioni vengono eseguite se e solo se
% esiste un link tra i due punti esaminati! Abbiamo, cosi', disegnato il nostro poligono.
end % chiudo l'if ed i due for
end
end
axis square
print -dpdf plot1.pdf


		 

class=zeros(1,n); % Questo e' il vettore delle etichette, ovvero un vettore riga con n
% componenti. La i-esima componente fornisce l'etichetta del punto i-esimo. Abbiamo tre
% valori per l'etichetta: '0' se il punto non e' stato ancora visitato, '1' se e' stato 
% visitato ma non assegnato, cioe' non e' ancora noto il percorso ottimo, ed infine '2'
% se si tratta proprio di un punto visitato ed assegnato. Per adesso abbiamo solo zeri,
% visto che dobbiamo ancora iniziare e nessun punto e' stato ancora esaminato.

bestpath=10^10*ones(1,n); % Vettore a n componenti che utilizzeremo per memorizzare il peso
% totale del percorso migliore dal punto init al punto fin. Lo inizializziamo con un numero molto grande.

init=1; % Abbiamo scelto come punto init quello che ha indice 1
class(init)=2; % Diamo al punto di partenza init l'etichetta di assegnato.
prec(init)=init; % Poiche' un qualsiasi sotto-percorso di un percorso ottimale e' ottimale,
% per ricostruire i cammini ottimali, basta associare ad un punto appena assegnato
% quello assegnato immediatamente prima.
bestpath(init)=0; % Il percorso ottimale da init ad init ha peso zero.
ultimo=init; % Ogni volta avremo un ultimo punto assegnato, che adesso e' init.

for k=2:n % Effettuiamo le iterazioni. Avrei messo un while (ultimo diverso da fin)
% se avessi voluto calcolare solo il percorso ottimale da init a fin.

		  for j=1:n
		  if class(j) < 2 & A(ultimo,j) > 0 % Prolunghiamo il percorso ottimale
% che arrivava fino all'ultimo punto che abbiamo assegnato. Se il nostro potenziale punto 
% di prolungamento del percorso ancora non e' stato assegnato ed esiste il link tra l'ultimo
% assegnato ed esso, prolunghiamo e calcoliamo la distanza del percorso prolungato.
                  dd=bestpath(ultimo)+dist(ultimo,j); % calcoliamo la nuova distanza aggiungendo
% alla lunghezza del percorso ottimale fino all'ultimo punto assegnato (bestpath(ultimo)), il
% peso tra ultimo ed il punto di prolungamento (j).
		  if class(j) == 0 % Se e' la prima volta che visitiamo il punto j, 
                  bestpath(j)=dd; % gli assegniamo la distanza migliore al momento da init,
                  class(j)=1;  % gli assegnamo l'etichetta 1,
                  prec(j)=ultimo; % e come punto precedente gli assegniamo ultimo.
                  else
		    if dd < bestpath(j) % Se invece j e' un punto gia' visitato ma non assegnato,
% allora facciamo il check seguente per evitare di scegliere un percorso piu' lungo.
                    bestpath(j)=dd;
                  prec(j)=ultimo;
                  end % chiudo i tre if
                  end 
                  end	
                end % chiudo il secondo for ed ho fatto tutti i possibili prolungamenti.
		  distmin=10^10;
		  for j=1:n % Con questo ciclo determino quale punto tra quelli visitati ma non
% ancora assegnati, ha la distanza minima da init.
		  if class(j) == 1 & bestpath(j) < distmin
                  ultimo=j; % questo e' il nostro "ultimo" punto assegnato
                  distmin=bestpath(j);
                  end
                  end   
                  class(ultimo)=2; % cambiamo etichetta ad ultimo.
end
prec
		  fin=6; % punto finale fin.
% di seguito ricostruisco il percorso al contrario da fin ad init
                  s=1;
                  j=fin;
                  path(s)=j; 
                  while abs(prec(j)-j) >  0 % questo accade solo per il punto init 
                  s=s+1;
		  path(s)=prec(j);
                  j=prec(j);
                  end
path

figure
hold on
		  for i=1:n
		  plot(x(1,i),x(2,i),'x')% Facciamo il plot dei nodi del grafo. Metto la 'x'
% per disegnare solo i punti senza congiungerli.
end
		  for k=1:length(path)-1 % ciclo for per plottare il percorso ottimale da init a fin.
		    plot([x(1,path(k)) x(1,path(k+1))],[x(2,path(k)) x(2,path(k+1))])
% plotta per ogni k un segmento che congiunge i due punti path(k) e path(k+1). In questo modo
% disegna proprio il cammino trovato dall'algoritmo.
end
axis square
print -dpdf plot2.pdf