Algoritmo di Bellman-Ford

[Ing._Claudio_Fontana]

Noto algoritmo di instradamento che data una "routing table" genera i cammini ottimi che uniscono un nodo sorgente a tutti gli altri nodi. La routing table è così definita: l'elemento di posto (i,j) rappresenta il costo di collegamento tra il nodo i e il nodo j (nella direzione i->j). I costi si intendono tutti non negativi ed un costo pari a "-1" indica un collegamento interrotto. Il programma restituisce le sequenze di cammino ottimo tra il nodo sorgente e tutte le altre destinazioni e mappa su una picture il grafo della tabella di instradamento e i grafi dei cammini ottimi. I nodi del grafo sono disposti su un reticolo regolare e può essere cambiato sia l'ordine sia il numero di nodi per riga. I nodi sono rappresentati graficamente come dischi al cui centro è riportato il numero del nodo mentre gli archi sono dei segmenti tangenti ai nodi orientati e pesati. L'orientamento è destrorso dal nodo di partenza mentre il peso indica il costo del collegamento ed è rappresentato da un numero che si trova all'estremità del segmento in prossimità del nodo di destinazione.