Использование BFS для взвешенных графиков

Я пересматривал алгоритмы кратчайшего пути из одного источника, и в видео учитель упоминает, что BFS/DFS нельзя использовать непосредственно для поиска кратчайших путей в взвешенном графике (я думаю, что все это уже знают), и сказал, чтобы выяснить причину твой собственный.

Мне было интересно узнать точную причину / объяснение того, почему его нельзя использовать для взвешенных графиков. Это из-за веса краев или что-то еще? Может кто-нибудь объяснить мне, как я немного смущен.

PS: я прошел этот вопрос и этот вопрос.

Источник

3 ответа

Решение

Рассмотрим график, подобный этому:

A---(3)-----B
|           |
\-(1)-C--(1)/

Кратчайший путь от A до B - через C (с общим весом 2). Обычная BFS будет проходить путь непосредственно от A до B, отмечая B как видимый, и от A до C, отмечая C как видимый.

На следующем этапе распространение от C, B уже помечено как видимое, поэтому путь от C до B не будет рассматриваться как потенциально более короткий путь, и BFS сообщит вам, что кратчайший путь от A до B имеет вес из 3.

Вы можете использовать алгоритм Дейкстры вместо BFS, чтобы найти кратчайший путь на взвешенном графике. Функционально алгоритм очень похож на BFS и может быть написан аналогично BFS. Единственное, что меняется, - это порядок, в котором вы рассматриваете узлы.

Например, на приведенном выше графике, начиная с A, BFS обработает A -> B, затем A -> C и остановится на этом, потому что все узлы были замечены.

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

  1. Рассмотрим A -> C (так как это вес самого нижнего ребра из A)
  2. Рассмотрим C -> B (так как это ребро с наименьшим весом из любого узла, которого мы достигли до сих пор, что мы еще не рассмотрели)
  3. Рассмотрите и игнорируйте A -> B, так как B уже был замечен.

Обратите внимание, что разница заключается просто в том порядке, в котором проверяются ребра. BFS будет рассматривать все ребра от одного узла до перехода к другим узлам, в то время как алгоритм Дейкстры всегда будет учитывать невидимое ребро с наименьшим весом из множества ребер, связанных со всеми узлами, которые были замечены до сих пор. Это звучит странно, но псевдокод очень прост:

create a heap or priority queue
place the starting node in the heap
dist[2...n] = {∞}
dist[1] = 0
while the heap contains items:
   vertex v = top of heap
   pop top of heap
   for each vertex u connected to v:
       if dist[u] > dist[v] + weight of v-->u:
           dist[u] = dist[v] + weight of edge v-->u
           place u on the heap with weight dist[u]

Этот GIF из Википедии обеспечивает хорошую визуализацию того, что происходит:

Дейкстра

Обратите внимание, что это выглядит очень похоже на код BFS, единственное реальное отличие - это использование кучи, отсортированной по расстоянию до узла, вместо обычной структуры данных очереди.

Источник

Хотя это правда, но вы могли бы использовать BFS/DFS в взвешенных графиках с небольшим изменением в графике, если веса вашего графика положительные целые числа, вы можете заменить ребро весом n с n лезвия весом 1 с n-1 средние узлы. Что-то вроде этого:

A-(4)-B

будет:

A-(1)-M1-(1)-M2-(1)-M3-(1)-B

И не учитывайте эти средние узлы (например, M1,M2,M3) в ваших окончательных результатах BFS/DFS.

Эта сложность алгоритма равна O(V * M), а M - максимальный вес наших ребер, если мы знаем, что в наших конкретных графах M<log V этот алгоритм может быть рассмотрен, но в целом этот алгоритм может не иметь такой хорошей производительности.

Источник

учитель упоминает, что BFS / DFS нельзя использовать напрямую для поиска кратчайших путей на взвешенном графе

Во-первых, DFS не используется и вообще не работает с кратчайшими путями.

Во-вторых, этот ответ правильно объясняет, почему BFS не работает на взвешенных графах с циклами, и предлагает вариант Дейкстры , заменяя очередь очередью с приоритетом и позволяя расслабиться, если будет найден новый, более короткий путь к узлу.

Однако не упоминалось, что на взвешенном ориентированном ациклическом графе (взвешенный DAG ) алгоритм Дейкстры является излишним, и кратчайший путь с одним источником можно найти в O(|V|+|E|)времени, расслабляя каждую вершину в топологическом порядке. Этот подход также работает для групп DAG с отрицательными краями веса.

Вот алгоритм высокого уровня:

      distances = {V: infinity for V in vertices}
predecessors = {V: None for V in vertices}

for U in topological_sort(vertices):
    for V in adjacencies(U):
        if distances[V] > distances[U] + edge_weight(U, V): # relax the edge
            distances[V] = distances[U] + edge_weight(U, V)
            predecessors[V] = U

Источники:

Источник
Другие вопросы по тегам