Want to create interactive content? It’s easy in Genially!
Get started free
Algoritmi MST
MANUEL FRUCI
Created on January 30, 2025
Start designing with a free template
Discover more than 1500 professional designs like these:
Transcript
>
<
Algoritmi MST
per il calcolo di percorso minimo in un grafo
iniziA!
FRANCESCO MANCUSO MANUEL FRUCI GIULIA VAMPORE Classe 4E - A.S. 2024/2025
Routing
RIEPILOGO
Un router è un elaboratore che permette l'instradamento di pacchetti tra reti diverse. L'indirizzamento dei pacchetti avviene in modo:
DIRETTO: Quando nella comunicazione non c'è necessità di un router. INDIRETTO: Quando è coinvolto almeno un router nella comunicazione.
La rete è formata da diversi nodi. Per ottimizzare il traffico di rete, utilizziamo degli algoritmi che si basano sui costi delle varie tratte, i quali variano continuamente nel tempo.
Avanti
Tabella di Routing
RIEPILOGO
Una tabella di routing è una struttura dati utilizzata dai router per memorizzare informazioni sui percorsi disponibili per raggiungere diverse reti. Essa consente al router di determinare il miglior percorso per inviare pacchetti di dati verso la loro destinazione (nel caso di routing indiretto).
Una tipica tabella di routing contiene le seguenti colonne:
Destinazione: Indica l'IP rete o dell'host di destinazione
Subnet Mask: Relativa all'IP di destinazione
Next-Hop: L'indirizzo IP del nodo successivo al quale inviare i dati
Interfaccia: L'interfaccia di rete del router
Costo: Un valore che indica il costo del percorso, usato negli algoritmi
Avanti
Cos'è un Grafo?
RIEPILOGO
Un grafo è una struttura utilizzata per rappresentare relazioni tra oggetti. In particolare, nei contesti di sistemi e reti, un grafo è composto da: Nodi (o vertici): rappresentano gli oggetti o entità della rete Archi (o lati): rappresentano le connessioni o relazioni tra i nodi I grafi sono usati negli algoritmi di routing per determinare il percorso migliore per trasmettere dati attraverso una rete. Permettono di analizzare la connettività, identificare punti vulnerabili e ottimizzare le prestazioni.
Consideriamo 3 tipi di Grafi: Grafo orientato: Gli archi hanno una direzione, indicando il flusso di comunicazione (ad esempio, da un dispositivo a un altro).Grafo non orientato: Gli archi non hanno direzione, indicano una relazione bidirezionale fra i nodi.Grafo pesato: Gli archi hanno un "peso" associato, che può rappresentare il costo, il tempo o la larghezza di banda della connessione.
Avanti
Cos'è un Algoritmo?
RIEPILOGO
Un algoritmo è una sequenza di istruzioni o passi logici che vengono seguiti per risolvere un problema o compiere un' operazione. Nel caso delle Reti, utilizziamo gli Algoritmi di Dijkstra e Bellman Ford per determinare il "Minimum Spanning Tree"
Avanti
Algoritmo di Dijkstra
RIEPILOGO
L'algoritmo di Dijkstra permette di calcolare il MST per configurare le tabelle di routing: data la sua natura statica, se cambia la configurazione della rete è necessario ricalcolare l'albero dei cammini minimi ripartendo da capo.
Clicca qui per vedereil codice intero
È un algoritmo di tipo centralizzato in quanto ciascun nodo calcola il cammino ottimo da sé stesso verso tutti gli altri nodi in modo indipendente, partendo unicamente dalle informazioni complete sulla topologia della rete e sulle caratteristiche dei collegamenti.
Genera una tabella dei risultati che conterrà il costo minimo trovato e il nodo precedente. Durante l'analisi, i nodi una volta analizzati non vengono ri-considerati. A parità di costo minimo calcolato, si possono generare diversi MST, tutti validi ai fini di ottimizzazione.
Avanti
Algoritmo di Bellman Ford
RIEPILOGO
L'algoritmo di Bellman-Ford è un algoritmo distribuito che calcola per ciascun nodo il cammino migliore (e quindi definisce la sua tabella di routing) verso tutti i nodi presenti sulla rete in base a informazioni che riceve dagli altri nodi, senza avere la conoscenza della topologia della rete: un nodo conosce e comunica solo con i nodi direttamente connessi con lui.
Clicca qui per vedereil codice intero
Anche questo algoritmo genera una tabella dei risultati che conterrà il costo minimo trovato e il nodo precedente. Durante l'analisi, tutti i nodi vengono considerati e iterati, effettuando i calcoli per i costi minimi. A parità di costo minimo calcolato, si possono generare diversi MST, tutti validi ai fini di ottimizzazione. L'algoritmo ha un'iterazione continua fin quando non si verificano più modifiche alla tabella finale.
Avanti
Il nostro Programma
RIEPILOGO
Main.javaContiene l'inizio del programma con le chiamate alle funzioni delle altre classi.
CheckMatrice.java Contiene 3 metodi statici booleani, per controllare se la matrice è quadrata,simmetrica e se i nodi dichiarati nel file coincidono con la dimensione.
Matrice.java Gestisce la scelta da input (inserimento da tastiera, lettura da file o generazione)
BellmanFord.java e Dijkstra.java Ciascuna classe contiene il metodo void doIt() che, passata una matrice già controllata precedentemente, stampa il risultato dell'algoritmo.
LetturaFile.java Gestisce la lettura da file usando i Token
LetturaInput.java Riunifica lo scanner sotto un'unica classe, per ottimizzare il programma
Clipboard.java Contiene un solo metodo statico, per copiare negli appunti il risultato ottenuto.
Errore.java Riunifica la stampa degli errori con dettagli
Avanti
Riepilogo
RoutingTabelle di Routing Grafo Algoritmo Algoritmo di Dijkstra Algoritmo di Bellman-Ford Il nostro programma
FINE
FINE
GRAZIE PER L'ATTENZIONE
FRANCESCO MANCUSO MANUEL FRUCI GIULIA VAMPORE Classe 4E - A.S. 2024/2025