Register to reply 
Dijkstra's algorithm proof? 
Share this thread: 
#1
Jun2506, 08:08 PM

P: 168

Does anyone here know how to prove this? I'm stuck on how to even get this started.
Let G be a connected, weighted and undirected graph where all edges have a weight of 1. Prove that if Dijkstra's algorithm is run on this graph, G, then the tree returned is a breadthfirst tree. 


#2
Jun2606, 02:02 AM

Sci Advisor
HW Helper
P: 2,586

Everything I've read about Dijkstra's algorithm is that it finds the shortest path between vertices. What does it have to do with returning a breadthfirst tree? What does it even have to do with trees? You're talking about G, a graph, not necessarily a tree.



#3
Jun2606, 02:07 AM

Sci Advisor
P: 1,253

Well, as far as I know there's no such thing as a "breadthfirst" tree. Breadthfirst describes the manner in which the tree is traversed. In Dijkstra's algorithm I'm not sure what the question intends because the tree is not traversed, but constructed. And nothing about the order in which the tree is constructed corresponds to any breadthfirst traversal of anything.
My final guess on what the question means is this. Let v1, v2, ... , vn be an ordering of the vertices of G in nondecreasing order by distance from the source. Then v1, v2, ... vn is a breadthfirst traversal of the shortestpaths tree returned by Dijkstra's algorithm. So, if you think that's what's being asked, what does it mean for a traversal NOT to be breadthfirst? Taking the correctness of Dijkstra's algorithm as given, why won't that happen in this case? 


Register to reply 
Related Discussions  
Dijkstra's Algorithm  Precalculus Mathematics Homework  0  
Dijkstra's algorithm  Set Theory, Logic, Probability, Statistics  0  
Algorithm  Calculus & Beyond Homework  6  
Graph Theory: Dijkstra's Algorithm  General Math  2  
Ln(x) algorithm  General Math  2 