my bfs code is this:
def bfs(graph, source, distance: dict):
queue = [source]
visited = [source]
distance[source] = 0
while queue:
deVertex = queue.pop(0)
for neighbour in graph[deVertex]:
if neighbour not in visited:
queue.append(neighbour)
visited.append(neighbour)
distance[neighbour] = distance[deVertex] + 1
Here, the visited part comes immediately after we add the vertex to the queue
my dijkstra code is this:
def dijkstra(source):
heap = []
heappush(heap, [0, source])
distance[source] = 0
while heap:
dist, node = heappop(heap)
visited.add(node)
for child_dist, child_node in graph[node]:
if child_node not in visited and distance[child_node] > distance[node] + child_dist:
distance[child_node] = distance[node] + child_dist
heappush(heap, [distance[child_node], child_node])
Here, visited comes after we pop the vertex from the heap
I don't understand why answers are wrong in either of them when we change the visited position
i.e.
when putting visited after pop in bfs OR when putting visited after appending to the heap in dijkstra