Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
244 views
in Technique[技术] by (71.8m points)

dijkstra - Dijktra algorithm vs breath first search for shortest path in graph

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

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

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...