Алгоритм Беллмана — Форда
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
алгоритм поиска кратчайшего расстояния от данной вершины до всех остальных во взвешенном графе
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
- Named after
- L. R. Ford, Jr.
- Image
- Bellman–Ford algorithm example.gif
Show 5 more facts
- discoverer or inventor
- Edward F. Moore
- derivative work
- Babel
- Commons category
- Bellman–Ford algorithm
Sources (2)
via Wikidata · CC0
Article · Русский
Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. Алгоритм маршрутизации RIP (алгоритм Беллмана — Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
Abstract from DBpedia / Wikipedia · CC BY-SA