it’s not relevant for the test case, but should it be added “visited.add(root);” right before the while?
I think so too.
it’s is already added when she initialized the set
11 visited = set([root])
For those who are trying out their own code,
if you are seeing “NameError: name ‘List’ is not defined”, just add “from typing import List” to the top of the script.
Maybe typo:
BFS is best for finding distance between to nodes since it traverses level by level.
→
BFS is best for finding distance between two nodes since it traverses level by level.
Thanks for pointing out.
the main() function for JavaScript doesn’t pass in any params, so the tests never pass
function* main() {
const res = shortestPath();
console.log(res);
}
The input specified in the description is a Dict[List[int]], yet the formal parameters of the code have the typing set to List[List[int]]. There’s a disconnect there and wouldn’t be analogous for keys that aren’t 0-indexed.
why the graph if of type List[List[int]], I thought it is a dict instead of a 2d array
hi, what are the parameters to use for the javascript test case?
Problem: Find distance between two nodes.
Solution: Finds the distance between ROOT and a node.
The solution does not solve the stated problem.
You need a variable for both ‘firstNodeLevel’ and ‘secondNodeLevel’ and set the current level to these variables if the target value matches the current node value.
Then call return abs(secondNodeLevel - firstNodeLevel) to get the solution, or return -1 if either of the variables are -1 (variables are -1 if not contained in graph)
I’m confused, should graph be a dict instead of a list?
Nodes of the graph start with index 0, so we can use a list here. You can name each node and use dict instead, but there is no difference.
q = deque([[a, 0]])
visited = set()
while q:
node, level = q.popleft()
for n in graph[node]:
if n == b:
return level + 1
if n not in visited:
q.append([n, level + 1])
visited.add(n)
I am confused as to where the getNeighbors function is coming from.
getNeighbors(node) returns the neighbors of the node. In this problem, it simply returns the corresponding nodes in the adjacency list.
Yeah, you’re right. I think this python solution solves the stated problem (returning None when a node is not in the graph). Also assumes 0 indexed nodes, which seems like something we can’t get around given the way the input is supplied.
def shortest_path(graph: List[List[int]], a: int, b: int) -> int:
def get_neighbors(i):
return graph[i]
def bfs(node1, node2):
queue = deque([0])
level = 0
visited = set([0])
first_node_level = None
second_node_level = None
while queue:
n = len(queue)
for _ in range(n):
node = queue.popleft()
if node == node1:
first_node_level = level
elif node == node2:
second_node_level = level
if first_node_level is not None and second_node_level is not None:
return abs(first_node_level - second_node_level)
for neighbor in get_neighbors(level):
if neighbor in visited:
continue
queue.append(neighbor)
visited.add(neighbor)
level += 1
return bfs(a, b)
Typo:
Again we adopt the convention that n denote the number of nodes in the graph and m the numebr of edges.
should be
Again we adopt the convention that n denote the number of nodes in the graph and m the number of edges.
“for neighbor in get_neighbors(level):” should be “for neighbor in get_neighbors(node):”