Shortest Path in Graph
BFS searching shortest path
Well done! Now, let's implement a method that helps us to find the length of shortest path between two vertices, i. e. minimum number of edges to reach end vertice from start.
You should store the length of the way from start to curr node, and you can do it by modifying visited array: visited[i] equals:
-
-1, if
inot visited yet -
0, if
iis visited as first node -
1, if
iis a neighbor of node, that has mark0 -
k, if
iis a neighbor of node with mark k-1 etc.
This way, you'll store the distance between start and current node, like at the example:
So, the answer is a visited[end].
Swipe to start coding
bfs(start, end) returns a number of edges between start and end nodes. If there is no path, return -1.
Actually this method does traverse as BFT method, but until the end vertex is found. Copy & Paste your BFT algorithm, and add some changes.
Tak for dine kommentarer!
single
Spørg AI
Spørg AI
Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat
Opsummér dette kapitel
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 7.69Shortest Path in Graph
Stryg for at vise menuen
BFS searching shortest path
Well done! Now, let's implement a method that helps us to find the length of shortest path between two vertices, i. e. minimum number of edges to reach end vertice from start.
You should store the length of the way from start to curr node, and you can do it by modifying visited array: visited[i] equals:
-
-1, if
inot visited yet -
0, if
iis visited as first node -
1, if
iis a neighbor of node, that has mark0 -
k, if
iis a neighbor of node with mark k-1 etc.
This way, you'll store the distance between start and current node, like at the example:
So, the answer is a visited[end].
Swipe to start coding
bfs(start, end) returns a number of edges between start and end nodes. If there is no path, return -1.
Actually this method does traverse as BFT method, but until the end vertex is found. Copy & Paste your BFT algorithm, and add some changes.
Skift til skrivebord for at øve i den virkelige verdenFortsæt der, hvor du er, med en af nedenstående mulighederTak for dine kommentarer!
Awesome!
Completion rate improved to 7.69single
