0-1 BFS and Dijkstra doubt

Revision en1, by 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?

Tags 0-1 bfs, dijkstra, stupid, doubt

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English B0JACK 2021-03-16 00:38:02 642 Initial revision (published)