Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Dijkstra's algorithm proof?

  1. Jun 25, 2006 #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. Jun 26, 2006 #2


    User Avatar
    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. Jun 26, 2006 #3


    User Avatar
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook