Ответ 1
Рассмотрим такой граф:
A---(3)-----B
| |
\-(1)-C--(1)/
Самый короткий путь от А до В - через С (с общим весом 2). Нормальная BFS будет принимать путь непосредственно от A до B, отмечая B как видно, и от A до C, отмечая C как показано.
На следующем этапе распространение с C, B уже отмечено как показано, поэтому путь от C до B не будет рассматриваться как потенциальный более короткий путь, и BFS скажет вам, что кратчайший путь от A до B имеет вес 3.
Вы можете использовать алгоритм Dijkstra вместо BFS, чтобы найти кратчайший путь на взвешенном графике. Функционально алгоритм очень похож на BFS и может быть написан аналогично BFS. Единственное, что меняется, это порядок, в котором вы рассматриваете узлы.
Например, в приведенном выше графике, начиная с A, BFS будет обрабатывать A → B, затем A → C и останавливаться там, потому что все узлы видны.
С другой стороны, алгоритм Дейкстры будет работать следующим образом:
- Рассмотрим A → C (так как это вес самого нижнего края из A)
- Рассмотрим C → B (так как это край наименьшего веса из любого node, который мы до сих пор до сих пор не рассмотрели)
- Рассмотрим и проигнорируем A → B, так как B уже был замечен.
Заметим, что разница лежит в том порядке, в котором проверяются ребра. BFS рассмотрит все ребра из одного node, прежде чем переходить к другим узлам, тогда как алгоритм Дийкстра всегда будет рассматривать край наименьшего веса невидимый, из набора ребер, связанных с all узлы, которые были просмотрены до сих пор. Это звучит запутанно, но псевдокод очень прост:
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, Единственная реальная разница заключается в использовании кучи, отсортированной по расстоянию до node вместо обычной структуры данных очереди.. p >