I need some clarifications and inputts regarding Dijktra's algorithm
vs breath first search
in directed graphs, if these are correct.
Dijktra's
algorithm finds the shortest path from Node A
to Node F
in a weighted
graph regardless of if there is a cycle or not (as long as there are no negative weights)
but for that, All paths from A to all other Nodes in the graph are calculated and we grab the path from
Ato
Fby reversing the sequences of nodes in
prev`.
BFS: finds the shortest path from Node A
to Node F
in a non-weighted graph, but if fails if a cycle detected.
however, BFS
just calculates the path from Node A to Node F and not necessarily all path from Node A.
if Node F is reached early, it just returns the path.
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…