Can only be applied to a directed graph with each edge having (strictly) positive lengths.
BFS can only be used to find the shortest path in a graph with unit-length edges.
Implementation Example
Algorithm
In each iteration, the shortest path to one new vertex will be found from the source vertex.
Initialization
- X = {S} [vertices processed so far]
- A[S] = 0 [computed shortest path distances]
- B[S] = 0 [computed shortest paths]
BFS can only be used to find the shortest path in a graph with unit-length edges.
Implementation Example
Algorithm
In each iteration, the shortest path to one new vertex will be found from the source vertex.
Initialization
- X = {S} [vertices processed so far]
- A[S] = 0 [computed shortest path distances]
- B[S] = 0 [computed shortest paths]
No comments:
Post a Comment