Алгоритм Беллмана — Форда
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
Article · Русский
Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. Алгоритм маршрутизации RIP (алгоритм Беллмана — Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
Abstract from DBpedia / Wikipedia · CC BY-SA