Percorsi minimi
Viene qui proposto un esempio di applicazione del modello di
Floyd-Warshall.
Sul territorio circostante Mortara (AL) è stata sviluppata una
rete di 50 nodi con i relativi collegamenti. Tali collegamenti
sono stati tracciati sulla base delle vie di comunicazione
esistenti, mentre i nodi sono stati posti sui principali comuni
del circondario.
La rappresentazione grafica può essere effettuata utilizzando
un programma standard di disegno, in particolare software G.i.s.
In questo esempio si è usato AUTOCAD.
Il vantaggio fornito da questi programmi è la possibilità di
misurare le distanze fra i nodi in maniera automatica ed
iterabile; la compilazione della matrice delle distanze risulta
quindi molto semplificata e velocizzata.
La matrice di ingresso all' algoritmo di Floyd è la matrice
dei costi.
Tale matrice è costituita dalle distanze in Km tra i vari nodi,
quindi cij=dij .
La matrice delle distanze può essere in realtà costruita nei
due seguenti modi:
· IN FORMA MATRICIALE.
E' una matrice n x n (n = numero di nodi della rete).
Agli archi non fisicamente esistenti è stato assegnato un valore
dij= infinito (in pratica un valore dij = 9999).
Visualizza matrice dei dati
· SU TRE COLONNE.
Tale matrice è costituita da tre colonne,
divise l' una dall' altra dal simbolo " ; "
- la prima colonna rappresenta il nodo origine ;
- la seconda rappresenta il nodo destinazione ;
- la terza rappresenta la distanza tra origine e destinazione.
Visualizza matrice 3 colonne
Attraverso l' algoritmo sarà cosi ' possibile calcolare sia
la distanza minima e il relativo percorso tra un nodo origine e
un nodo destinazione qualsiasi, sia l'intera matrice che mostra
il collegamento tra ogni nodo e tutti gli altri.
Visualizzazione matrice dei risultati (output).
Se si possiede Excel 2000:
- aprire in Excel il file di output con la modalità: "Tutti
i file"
- nella finestra "Tipo dati originali " selezionare
"Delimitati"
- cliccare su "Avanti "
- scegliere come delimitatore il punto e virgola
- ciccare su " Avanti "
- selezionare "Avanzate" e scegliere come separatore
dei decimali la virgola e come separatore delle migliaia lo
spazio vuoto
- ciccare su "ok"
- cliccare su "Fine".
Se non si possiede Excel 2000:
- aprire il file di output in Word
- scegliere dal menù "Modifica" il comando
"sostituisci"
- dove si ha "Trova" mettere il punto e dove si ha
"sostituisci con" mettere la virgola
- riaprire il file in excel .
Si può notare come l' algoritmo qui utilizzato sia molto efficiente, in quanto trova la soluzione in meno di 1 secondo.
 |
 |
 |
