Damn...you're so underrated...I watched so many videos on the topic and yours was the only one that I found helpful. Thanks a lot, dude..for uploading this.
This cannot be used to find the shortest path. For the input d = { 1: [2, 3], 2: [1, 3], 3: [1, 2] } and the shortest path between 1 and 3, It returns [1, 2, 3] as the shortest path instead of [1, 3]
Hello mate, got same problem with a bit more bigger graph. It will find the shortest path if we will swap 2 and 3 in your example (obviously it will change parent of 3). But I cant figure out what's wrong with algorithm, im pretty sure I miss something simple. Do you have thoughts where to dig? Thanks anyway. Edit. This is works. def bfs(graph, start, end): visit = {k: False for k in graph.keys()} parent = {k: None for k in graph.keys()} q = Queue() visit[start] = True q.put(start) while not q.empty(): x = q.get() for v in graph[x]: if not visit[v]: visit[v] = True parent[v] = x q.put(v) return short(parent, start, end) def short(parent, start, end): path = [] while end is not None: path.append(end) end = parent[end] return path[::-1]
I think the issue could be fixed if we put after line 12 (in bfsShortestPath) the check that the neighbor node is the endNode, and in that case break the loop. for example if you add after line 12: if neighbor == endNode: return shortestPath(parentNodes, startNode, endNote) Then it works
What if we want to set a goal node so instead of wanting the algorithm to read all the nodes we have a destination node we want it to stop at how do we factor that in into the code ?
I think you could pass in a parameter for goalnode and check if your current node is equal to that, now if you want the shortest path to that node then he shows that implementation
def dfs(graph,startNode): visitedNodes = [] queue = [startNode] while queue: currentNode = queue.pop() if currentNode not in visitedNodes: visitedNodes.append(currentNode) for neighbour in reversed(graph[currentNode]): if neighbour not in visitedNodes: queue.append(neighbour) return visitedNodes ^Depth-search (use chatgpt for this)
Damn...you're so underrated...I watched so many videos on the topic and yours was the only one that I found helpful. Thanks a lot, dude..for uploading this.
This cannot be used to find the shortest path. For the input d = {
1: [2, 3],
2: [1, 3],
3: [1, 2]
}
and the shortest path between 1 and 3,
It returns [1, 2, 3] as the shortest path instead of [1, 3]
Hello mate, got same problem with a bit more bigger graph. It will find the shortest path if we will swap 2 and 3 in your example (obviously it will change parent of 3). But I cant figure out what's wrong with algorithm, im pretty sure I miss something simple. Do you have thoughts where to dig?
Thanks anyway.
Edit.
This is works.
def bfs(graph, start, end):
visit = {k: False for k in graph.keys()}
parent = {k: None for k in graph.keys()}
q = Queue()
visit[start] = True
q.put(start)
while not q.empty():
x = q.get()
for v in graph[x]:
if not visit[v]:
visit[v] = True
parent[v] = x
q.put(v)
return short(parent, start, end)
def short(parent, start, end):
path = []
while end is not None:
path.append(end)
end = parent[end]
return path[::-1]
I think the issue could be fixed if we put after line 12 (in bfsShortestPath) the check that the neighbor node is the endNode, and in that case break the loop.
for example if you add after line 12:
if neighbor == endNode:
return shortestPath(parentNodes, startNode, endNote)
Then it works
this version of bfs code only works for graphs without cycles, else u need to change the code
Pls dfs as well
What if we want to set a goal node so instead of wanting the algorithm to read all the nodes we have a destination node we want it to stop at how do we factor that in into the code ?
I think you could pass in a parameter for goalnode and check if your current node is equal to that, now if you want the shortest path to that node then he shows that implementation
Must watch 2020
Dfs???
def dfs(graph,startNode):
visitedNodes = []
queue = [startNode]
while queue:
currentNode = queue.pop()
if currentNode not in visitedNodes:
visitedNodes.append(currentNode)
for neighbour in reversed(graph[currentNode]):
if neighbour not in visitedNodes:
queue.append(neighbour)
return visitedNodes
^Depth-search (use chatgpt for this)
i copied everything but got ['0', '4', '1', '5'] as a result