algoritmo di Bellman–Ford

Also known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm

algoritmo per trovare in un grafo con pesi negativi il percorso più breve da una sorgente singola

In the Vinony graph

Vinony's link graph records 173 inbound references to algoritmo di Bellman–Ford, and connects out to shortest path problem, International Standard Book Number and algorithm.

Vinony files it under Dynamic programming, Graph algorithms and Graph distance.

Vinony links it to 29 Wikipedia language editions.

Key facts

Class: Single-source shortest path problem (for weighted directed graphs)
Data structure: Graph
Worst case performance: Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
Best case performance: Θ ( | E | ) {\displaystyle \Theta (|E|)}
Worst case space complexity: Θ ( | V | ) {\displaystyle \Theta (|V|)}

via Wikipedia infobox

Wikidata facts

Image: Bellman–Ford algorithm example.gif

Show 1 more fact

Commons category: Bellman–Ford algorithm

Sources (2)

via Wikidata · CC0

Article · Italiano

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.

Abstract from DBpedia / Wikipedia · CC BY-SA