Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
menu search
person
Welcome To Ask or Share your Answers For Others

Categories

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 fromAtoFby reversing the sequences of nodes inprev`.

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.

enter image description here

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
239 views
Welcome To Ask or Share your Answers For Others

1 Answer

Dijkstra doesn't search all nodes of the graph. When it has found a way from A to F and is sure there is no shorter one (because the outer border of the already visited nodes is farther away), it stops. This is possible without negative weights.

So to answer your question "if these are correct": They are not.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
...