Metraipolis › archive › dc_babc8d9006bd

Algoritmo di Floyd-Warshall — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T16:43:54.880Z
SHA-256 of the archived text
6021058b04831f281b7cd254311c48fc841e238ff6b606cb5ec6633bbde2b10d
Stable URL of this page
https://metraipolis.com/documento/dc_babc8d9006bd

How to cite

Algoritmo di Floyd-Warshall — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_babc8d9006bd (Metraipolis archive dc_babc8d9006bd, sha256 6021058b04831f281b7cd254311c48fc841e238ff6b606cb5ec6633bbde2b10d)
BibTeX
@misc{dcbabc8d9006bd,
  title = {Algoritmo di Floyd-Warshall — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_babc8d9006bd; sha256 6021058b04831f281b7cd254311c48fc841e238ff6b606cb5ec6633bbde2b10d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

L'algoritmo di Floyd-Warshall calcola il cammino minimo per tutte le coppie di un grafo pesato e orientato con una complessità O ( | V | 3 ) {\displaystyle O(\left|V\right|^{3})} . L'idea alla base di questo algoritmo è un processo iterativo che, scorrendo tutti i nodi, ad ogni passo h si ha (data una matrice A) nella posizione [i,j] la distanza - pesata - minima dal nodo di indice i a quello j attraversando solo nodi di indice minore o uguale a h. Se non vi è collegamento allora nella cella c'è infinito. Alla fine (con h = numero di nodi) leggendo la matrice si ricava la distanza minima fra i vari nodi del grafo. Premesso ciò, si può dire che il problema si risolve in programmazione dinamica facendo uso teoricamente di una matrice cubica dove le ordinate e le ascisse sono i e j, mentre h è la profondità. Praticamente, invece, possiamo usare una sola matrice reiterandola piano per piano in h. Si comincia col ricavare la matrice di adiacenza del grafo (infinito dove non vi è collegamento), poi basandoci su di essa cominciamo, in ogni passo h successivo si esaminano ogni cella[i,j] della matrice A: se la somma della distanza tra i ed il nuovo nodo in esame h sommata alla distanza fra h e j è minore della distanza direttamente fra i e j allora si sostituisce quest'ultimo con la precedente somma (per andare dal nodo i al nodo j mi conviene passare per il nodo h). Detto in modo un po' più formale se (Ah-1[i,h] + Ah-1[h,j]) < Ah-1[i,j] allora Ah[i,j] = (Ah-1[i,h] + Ah-1[h,j]) dove h è il piano che stiamo analizzando. Sotto potete vedere un algoritmo in pseudocodice del procedimento descritto: Inizializzazione int [0..n, 0..n] dist; for i := 1 to n for j := 1 to n dist[i][j] := Weight(i,j); dove Weight(i,j) è una funzione che riporta il peso dell'arco da i a j, 0 nel caso in cui i = j oppure infinito se non esiste un arco da i da j nel grafo. floydWarshall(int [0..n, 0..n] dist) { for h := 1 to n for i := 1 to n for j := 1 to n if (dist[i][j] > dist[i][h] + dist[h][j]) then dist[i][j] := dist[i][h] + dist[h][j];

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Algoritmo di Floyd-Warshall» — https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall
Wikidata Q1047576 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1047576
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_Floyd-Warshall?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 147131949, consultata il 2026-10-07T16:12:17.737Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 39f24b281f97d4eeed966e8853853b25c25774df905eb4d1d49e1e3bdb68b46d