С 60-х годов XX века может показаться, что в области поиска кратчайших путей не было значительного прогресса, поскольку Эдсгер Дейкстра предложил алгоритм, который даёт практически оптимальное решение.
Однако это не так — прогресс был, и придумано много интересного.
Хотя фокус сместился и на другие задачи.
Давайте разберёмся, что же нового придумали и как это используется в современных системах логистики.
Почему автора огорчает, что HOMM III не учитывает флаг единства при расчете путей, и кто эти люди на фотографии рядом с Дейкстро́й?
Прогресс в поиске кратчайших путей
- Алгоритм Дейкстры.
Эдсгер Дейкстра в 1959 году разработал алгоритм, который получил широкое распространение и используется до сих пор.
Алгоритм позволяет находить кратчайшее расстояние от одной вершины графа до всех остальных вершин.
Этот алгоритм называют «почти оптимальным», поскольку он работает за O (M log N), где M — количество рёбер,
N— количество вершин.
То есть этот алгоритм работает асимптотически оптимально.
- Более быстрые алгоритмы
С развитием вычислительной техники появились более быстрые алгоритмы, которые позволяют находить кратчайшие пути за меньшее время, чем алгоритм Дейкстры.
Например, в 2000
Сейчас читают: 28
5
