Metraipolis › archive › dc_ea99e68dc9d3

Algoritmo di Bellman-Ford — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Algoritmo_di_Bellman-Ford
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T13:24:03.882Z
SHA-256 of the archived text
9650ee4de374cc64a4afe6b71dff1aa0958fc017e451b3734506bf76fc0efc84
Stable URL of this page
https://metraipolis.com/documento/dc_ea99e68dc9d3

How to cite

Algoritmo di Bellman-Ford — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Bellman-Ford (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ea99e68dc9d3 (Metraipolis archive dc_ea99e68dc9d3, sha256 9650ee4de374cc64a4afe6b71dff1aa0958fc017e451b3734506bf76fc0efc84)
BibTeX
@misc{dcea99e68dc9d3,
  title = {Algoritmo di Bellman-Ford — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_Bellman-Ford},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ea99e68dc9d3; sha256 9650ee4de374cc64a4afe6b71dff1aa0958fc017e451b3734506bf76fc0efc84},
  year = {2026}
}

Archived text

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

L'algoritmo di Bellman-Ford calcola i cammini minimi di un'unica sorgente su un grafo diretto pesato (dove alcuni pesi degli archi possono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiede che i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archi negativi. Secondo Robert Sedgewick «i pesi negativi non sono solamente una curiosità matematica; […] si presentano in modo naturale quando riduciamo altri problemi a quelli di cammini minimi» e forniscono un esempio specifico di una riduzione dal problema NP-completo del cammino hamiltoniano. Se un grafo contiene un ciclo di peso totale negativo allora sono ottenibili pesi arbitrariamente piccoli e quindi non c'è soluzione; Bellman-Ford individua questo caso.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei giochi»).
Fonte: Wikipedia in italiano, voce «Algoritmo di Bellman-Ford» — https://it.wikipedia.org/wiki/Algoritmo_di_Bellman-Ford
Wikidata Q816022 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q816022
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_Bellman-Ford?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 151559379, consultata il 2026-10-07T12:55:31.179Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1ee835296302d986837da90915b7bb997f60be53a8478ce24e173da9c5a7f4be