Здравствуйте. В статье про bfs сказано, что Нахождение кратчайшего пути в 0-1-графе (т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди. Как проверить улучшение расстояние до какой-то вершины за рациональную асимптотику, и как дальше с этим работать, ведь та вершина, расстояние до которой улучшилось могла быть "подожжена" чуть ли не в самом начале, а тогда придется проходить все заново. UPDATE Пытался пойти путём другой статьи. Возникает вопрос: если есть ребра из вершины 1-2(вес 1) и 1-3(вес 0) и 3-2(вес 0) и 2-1(вес 0) то алгоритм от вершины 1 поставит dist2 = 1; dist[3] = 0; а от 3 к 2 перейти не сможет, т.к. она использована. Что делать?
Ответ
В этой модификации алгоритма не нужно использовать массив used. Для каждого ребра нужно проверять не нашелся ли путь лучше, чем тот, который уже найден для конечной вершины ребра. И если новый путь лучше, добавлять вершину в начало/конец очереди в зависимости от стоимости ребра. Нетрудно показать, что в любой момент времени в очереди могут находиться только вершины, расстояние до которых равно x и, возможно, x+1. Причем все вершины с расстоянием x идут раньше всех вершин с расстоянием x+1. Из этого следует, что любая вершина попадет в очередь не более двух раз. Доказательство: если при первом попадании в очередь, в очереди не осталось вершин с меньшим расстоянием, то добавленная вершина еще раз в очередь не попадет, так как не осталось вершин, способных срелаксировать расстояние до нее. Если же в очереди еще остались вершины с расстоянием меньшим на 1, то они смогут улучшить расстояние до добавляемой только 1 раз и тогда она попадет в очередь второй раз. Таким образом сохранится асимптотика O(N + M).
Комментариев нет:
Отправить комментарий