Комментарии 12
Подвох здесь чувствую я. Вы собрались в множестве из N элементов искать нужный за более чем O(n) операций???
Also, зачем вы говорите об ограничении снизу когда вас спрашивают об ограничении сверху?
А вот реальной применимости здесь не видно.
После еще нескольких перечитываний статьи я кажется начал понимать что хотел сказать автор.
Вот есть git bisect, который ищет между "хорошей" и "плохой" вершиной в DAG самую раннюю плохую. И минимизирует количество вопросов "является ли эта вершина плохой", т.к. время на получение ответа (который вообще может считаться вручную) непредсказуемо и предполагается много бОльшим чем обходы графа.
Автор хочет сделать что-то похожее, только в более общем виде — на произвольном графе.
В противном случае пусть e=(v,w) будет ребром, полученным в ответ на запрос; вычисляем множество всех вершин x∈V, для которых e является кратчайшим путём из v в x. Назовём это множество T.
И что вот здесь вот с big-O происходит?
self.distance_from_start[vertex] = new_distance
if new_distance < self.distance_from_start[vertex]:
Здесь ошибка. Присвоение, а потом сравнение с тем же самым значением.
Граф выглядит как дерево с равномерными весами
Хм тавтология какая то… Дерево это связный ациклический граф, следовательно выходит: граф выглядит как граф. Если смотреть оригинал:
Graph looks like this tree, with uniform weights
То тоже немного тавтологией отдает, но не так.
Двоичный поиск в графах