@VovanZ

Как написать алгоритм для для поиска кратчайшего расстояния?

Дан направленный ориентированный граф, нужно найти расстояние до всех вершин из заданной.
Понятно, что такая задача решается алгоритмом Дейкстры.

Однако, что если реализовать этот алгоритм проще? Что если добавлять вершины, для которых мы нашли лучший путь не в очередь с приоритетами, а в обычную очередь (FIFO) ?
Я понимаю, что такой алгоритм будет не оптимален.

Вопрос в следующем: будет ли он корректен? Если нет - просьба привести контрпример.
  • Вопрос задан
  • 2654 просмотра
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Тогда придётся повторно пересматривать вершины если для них нашёлся более короткий путь.
Пример:
.  A  B  C
A  -  4  1
B  4  -  1
C  1  1  -

Начальная точка A (A = 0). Строим пути из A (B = 4, C = 1), добавляем их в очередь. Строим пути из B (С = 1). Строим пути из C (B = 2). И снова надо перестраивать пути из B, поскольку до него нашёлся более короткий путь.
Поэтому у Дейкстры и используется сортированная очередь, тогда не возникает необходимости в повторном просмотре точек.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы