Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Learn Shortest Path in Graph | Practice
Breadth First Search

bookShortest 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 i not visited yet

  • 0, if i is visited as first node

  • 1, if i is a neighbor of node, that has mark 0

  • k, if i is 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].

Task

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.

Everything was clear?

How can we improve it?

Thanks for your feedback!

SectionΒ 2. ChapterΒ 3
single

single

Ask AI

expand

Ask AI

ChatGPT

Ask anything or try one of the suggested questions to begin our chat

Suggested prompts:

Summarize this chapter

Explain the code in file

Explain why file doesn't solve the task

close

Awesome!

Completion rate improved to 7.69

bookShortest Path in Graph

Swipe to show menu

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 i not visited yet

  • 0, if i is visited as first node

  • 1, if i is a neighbor of node, that has mark 0

  • k, if i is 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].

Task

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.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

close

Awesome!

Completion rate improved to 7.69
SectionΒ 2. ChapterΒ 3
single

single

some-alt