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

Question

[VovanZ]

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

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

Вопрос в следующем: будет ли он корректен? Если нет - просьба привести контрпример.

Answer 1

[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, поскольку до него нашёлся более короткий путь.
Поэтому у Дейкстры и используется сортированная очередь, тогда не возникает необходимости в повторном просмотре точек.

Comments

[VovanZ]

Да, я понимаю это. Я понимаю, что такой алгоритм не оптимален. Но корректен ли он? Будет ли найденное им решение правильным?

[Rsa97]

Будет, только в наихудшем случае работать он будет гораздо дольше. Наихудшая оценка сменится с N на N².

[Rsa97]

И, кстати, очередь всё равно не FIFO будет, при добавлении вершины в очередь надо проверить, что её там ещё нет.

[VovanZ]

@Rsa97 спасибо.
Я сейчас решаю задачи на сайте с проверяющей системой (подобной проверяющим системам для спортивного программирования, типа ACM) и получаю результат Wrong answer (а не Time limit exceeded), поэтому и задался этим вопросом.

[VovanZ]

@Rsa97 а что будет, если я одну вершину 2 раза добавлю в очередь? Случится что-то плохое?

[Rsa97]

Лишние раз пересчитывать, но ошибки вроде быть не должно.