0-1 BFS and Dijkstra doubt

Правка en1, от B0JACK, 2021-03-16 00:38:02

Hello all, sorry for this lame doubt, but I could not find any answer online.

Why is it that when implementing a 0-1 BFS, a visited array isn't necessary, while in Dijkstra it is necessary. According to cp-algorithm for dijkstra,

"Therefore we need to make a small modification: at the beginning of each iteration, after extracting the next pair, we check if it is an important pair or if it is already an old and handled pair. This check is important, otherwise the complexity can increase up to O(nm)."

Shouldn't the same be applicable to 0-1 BFS also? And if not, why do we require it for Dijkstra?

Теги 0-1 bfs, dijkstra, stupid, doubt

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский B0JACK 2021-03-16 00:38:02 642 Initial revision (published)