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

Предыдущий
вопрос Следующий
вопрос

Да, такой алгоритм будет некорректным, так как он может привести к неправильному результату. Рассмотрим следующий контрпример:

Пусть у нас есть граф с тремя вершинами A, B и C, где ребра имеют следующие веса: AB - 1, AC - 100, BC - 1. Начальная вершина - A.

Если мы будем использовать алгоритм с обычной очередью вместо очереди с приоритетами, то на первом шаге мы добавим вершину B в очередь, так как путь до неё короче, чем до вершины C. Затем мы перейдем в вершину B и добавим вершину C в очередь, так как путь до неё короче, чем до вершины A. Таким образом, мы найдем путь до вершины C с весом 2, в то время как кратчайший путь до неё имеет вес 1 (путь A -> B -> C).

Следовательно, использование обычной очереди вместо очереди с приоритетами приведет к неверному результату в некоторых случаях, что делает такой алгоритм некорректным.