I'm new in graph theory and need a little help. Let's say we have a graph with defined start and end vertext. How can I get the shortest path ONLY between the start and end vertex using BFS.

I've written a program that calculates the shortest path in the whole graph, but don't know how to implement it when I want to "restrict the tree" to only these vertices between start-end.

Any help, pseudo code, advice would be greatly appreciated.

有帮助吗?

解决方案

BFS algorithm gets a vertex in the graph and calculates shortest path from that vertex to all other vertices. When reaches some vertex BFS already have found the shortest path to it. So you dont need to continue algorithm if you need only shortest path to that vertex. You should finish the algorithm when it reaches the desired vertex.

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top