Блог пользователя sophisticated1

Shortest path using bfs
Автор sophisticated1, 12 лет назад, По-английски

To find shortest path in a directed graph with edges having weight either 0 or 1 , we often use a modification of bfs with deque. But i don't know why we push at head of the queue whenever we encounter a 0-weight edge ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

https://www.hackerearth.com/alkhwarizm15/algorithm/completing-mario/

This problem explains the scenario better.

This problem appeared in alkhwarizm 2015. Although i solved it using dijkstra but as you mentioned that this problem can be solved using bfs by pushing the 0 weight edge at the head of the queue.

idea is very very simple. When you know explore level X in the bfs all the nodes which are level X-1 are already in queue right ? In this case from level X you might have explored level X again with an edge having weight 0 and then X+1 using edge with weight 1. putting the X level node at the end of queue will lead to inconsistency as there might be a scenario in the queue like this {X,X+1,X,X+1} (entries represents levels) but if you put the level explored through edge weight 0 it will not hinder the consistency in the queue and preforms desired work

→ Ответить