Algoritme van Bellman-Ford
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
algorithm for finding single-source shortest paths in graphs, allowing some edge weights to be negative
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
Article · Nederlands
Het algoritme van Bellman-Ford is een graaf-algoritme dat, voor een gegeven knoop van een gerichte graaf, de kortste route naar alle knopen van die graaf bepaalt. Het algoritme van Dijkstra lost dit probleem sneller op, maar dat algoritme kan alleen gebruikt worden bij een graaf met niet-negatieve gewichten. Het algoritme van Bellman-Ford wordt dus in de praktijk alleen gebruikt bij een graaf met negatieve gewichten. Het algoritme van Bellman-Ford kan namelijk een negatieve cirkel opsporen. Het algoritme is genoemd naar zijn ontwikkelaars, en .
Abstract from DBpedia / Wikipedia · CC BY-SA