Algoritmo di Bellman-Ford

Lezione di Sistemi e reti per le classi quarte
Prof. Francesco Toscano - IIS "Giuseppe Peano" Torino

[ettorepan]

Devo confessare che all'inizio stavo chiudendo il video visto la lentezza e le cose dette veramente in forma banale, ma poi il video ha avuto una piega diversa, elaborando delle considerazioni molto utili allo studio di questo algoritmo.
Tuttavia scrivo qui sotto una mia breve sintesi su 25 minuti di video:
>Cos'è l'algoritmo di Bellman-Ford?
L'algoritmo di Bellman-Ford è utilizzato per cercare i cammini minimi di un'unica sorgente su un grafo diretto pesato.
Risulta molto simile all'algoritmo di Dijkstra, ma viene principalmente utilizzato quando ci sono pesi negativi sugli archi.

La prima differenza dall'algoritmo di Dijkstra è il fatto che l'algoritmo segue sempre un ordine; Può essere alfabetico, numerico o di altra convenzione, l'importante è che ci sia sempre un ordine.

La seconda differenza è che i pesi e i nomi dei nodi precedenti del cammino non vanno mai cancellati.

La terza differenza è che l'algoritmo prevede più iterazioni, cioè, bisogna ripetere lo stesso procedimento da capo, in modo da aggiornare gli eventuali nodi adiacenti precedentemente cambiati di peso.
La quarta differenza è che questo algoritmo è detto DINAMICO, in quanto può adattarsi al cambiamento di un peso di un nodo senza ricominciare da capo tutto, al contrario di Dijkstra che invece è detto STATICO perché al cambiamento di un peso di un nodo si deve per forza cancellare tutto e ricominciare da capo.

L'algoritmo termina quando si trova un'iterazione senza aggiornamenti.

Questo è quanto capito in generale e sentito in questo video, ancora sotto scrivo degli appunti sull'algoritmo di Dijkstra, in modo da facilitare chi legge questo commento da eventuali ricerche:
>Cos'è l'algoritmo di Dijkstra
L'algoritmo di Dijkstra è utilizzato per cercare i cammini minimi in un grafo con o senza ordinamento, ciclico e con pesi non negativi sugli archi.
Tale algoritmo non trova soltanto il cammino minimo, ma anche l'albero dei cammini minimi, in quanto al termine è calcolata la distanza assoluta di ogni nodo da quello di partenza.

*Procedimento:
Bisogna assegnare a ogni nodo un valore che chiameremo potenziale.
Ogni nodo ha all'inizio potenziale +∞.
Il nodo di partenza ha potenziale 0, nel senso che dista 0 da se stesso.
Ogni volta si sceglie il nodo con potenziale minore e lo si rende "definitivo" e si aggiornano i nodi adiacenti.
Il potenziale del nodo è dato dalla somma del potenziale del nodo precedente + il costo del collegamento.
Non si aggiornano i potenziali dei nodi resi definitivi.
I potenziali definitivi indicano la distanza di quel nodo da quello di partenza.
Quando si aggiorna il potenziale di un nodo si lascia quello minore.

**Struttura della tabella:
La tabella è strutturata in due parti;
La prima contiene i valori dei pesi di ogni nodo;
La seconda, chiamata "tabella dei precedenti", contiene il nome del nodo precedente a quello di riferimento.

L'algoritmo termina quando si toccano tutti i vertici.

Va indicato il cammino, il peso e le mosse.
Esempio, 1-3-6-5 per un totale di 20 in 3 mosse.

E con questo vi saluto, il professore di questo video mi corregga se ho sbagliato qualcosa. BYE

[niki]

Grazie mille, ho trovato il video molto utile per l'università😉

[giacintoadinolfi]

Grazie mille, mi a fatto superare un esame 😍

[matematicaonline]

Ricordi del mio primo anno di ingegneria informatica :’)

[andhy_bs]

consiglio: più veloce e meno complicato siccome è molto più facile di quel che stai dicendo