Dijkstra's algorithm proof?

  1. 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.
    Last edited: Jun 25, 2006
  2. jcsd
  3. AKG

    AKG 2,576
    Science Advisor
    Homework Helper

    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.
  4. 0rthodontist

    0rthodontist 1,249
    Science Advisor

    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?
    Last edited: Jun 26, 2006
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Dijkstra's algorithm proof?