Dijkstra's algorithm proof?

KataKoniK

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 breadth-first tree.

AKG

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 breadth-first tree? What does it even have to do with trees? You're talking about G, a graph, not necessarily a tree.

0rthodontist

Well, as far as I know there's no such thing as a "breadth-first" tree. Breadth-first 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 breadth-first 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 non-decreasing order by distance from the source. Then v1, v2, ... vn is a breadth-first traversal of the shortest-paths 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 breadth-first? Taking the correctness of Dijkstra's algorithm as given, why won't that happen in this case?