Ricerca operativa

Oggi vi spieghiamo come risolvere rapidamente gli esercizi in cui ci viene chiesto di applicare l’algoritmo di Floyd Warshall.

Il metodo mostrato nella dispensa grafi4 non è tra i più comodi ed è molto probabile sbagliare in quanto ci dobbiamo affidare completamente al grafo per risolvere l’esercizio. Con questo metodo invece non dovremmo neanche disegnarlo il grafo e praticamente il calcolo piu difficile da fare sarà decidere il minimo tra 2 numeri.

Nel pdf disponibile per il download abbiamo cercato di spiegare il metodo piu’ chiaramente possibile facendo anche un esempio con un esercizio d’esame, se avete dubbi non esitate a chiedere tra i commenti o su Facebook.

Download

Per chi ha il MAC o non riuscisse a visualizzare il file : Link alternativo

CORREZIONE : Se trovate un costo minore di quello in tabella il predecessore non è k ma bisogna andare a vedere nella tabella dei predecessori del passo precedente e prendere l’elemento k,j