Register to reply

Dijkstra's algorithm proof?

by KataKoniK
Tags: algorithm, dijkstra, proof
Share this thread:
KataKoniK
#1
Jun25-06, 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 breadth-first tree.
Phys.Org News Partner Science news on Phys.org
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space
AKG
#2
Jun26-06, 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 breadth-first tree? What does it even have to do with trees? You're talking about G, a graph, not necessarily a tree.
0rthodontist
#3
Jun26-06, 02:07 AM
Sci Advisor
P: 1,253
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?


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