Prev: Processing Emails Online!Earns $1000's Weekly!
Next: The strong non circular list argument.
From: Darren on 15 Jul 2010 06:44
Hi, I am new to this algorithm, and I read that the algorithm is
correct – i.e. will always produce the optimal minimum spanning tree.

As an experiment I tried the algorithm on a weighted graph, and got
two different results. Can somebody help me work out where I went
wrong?

Graph has labeled vertices A=(0,0), B=(10, 1), C=(20, -2), D=(30,0)

Now, if I start from C, I get C->D->B->A

But if I start from B, I get B->A->C->D.

These are two different trees?

Guess they would be equivalent if you closed the loop:
C->D->B->A->C
B->A->C->D->B
In which case, I think the usual proofs of correctness would be
correct.
From: Darren on 15 Jul 2010 07:25
On 15 July, 11:44, Darren <anon5...(a)yahoo.com> wrote:
> Hi, I am new to this algorithm, and I read that the algorithm is
> correct – i.e. will always produce the optimal minimum spanning tree.
>
> As an experiment I tried the algorithm on a weighted graph, and got
> two different results. Can somebody help me work out where I went
> wrong?
>
> Graph has labeled vertices A=(0,0), B=(10, 1), C=(20, -2), D=(30,0)
>
> Now, if I start from C, I get C->D->B->A
>
> But if I start from B, I get B->A->C->D.
>
> These are two different trees?
>
> Guess they would be equivalent if you closed the loop:
> C->D->B->A->C
> B->A->C->D->B
> In which case, I think the usual proofs of correctness would be
> correct.

Nevermind. I think the point is that the edges need to exist before
you apply the algorithm. It is not an algorithm for generating a
graph, it is an algorithm for generating shorted points between
vertices on an existing graph.
From: Ben Bacarisse on 15 Jul 2010 11:33
Darren <anon5874(a)yahoo.com> writes:

> Hi, I am new to this algorithm, and I read that the algorithm is
> correct – i.e. will always produce the optimal minimum spanning tree.
>
> As an experiment I tried the algorithm on a weighted graph, and got
> two different results. Can somebody help me work out where I went
> wrong?
>
> Graph has labeled vertices A=(0,0), B=(10, 1), C=(20, -2), D=(30,0)

Do you mean these are the geometric positions with weights equal to the
Euclidean distances between nodes? If so, you get this (approximate)
set of weights:

A B C D
A 0 10.05 20.1 30
B 10.05 0 10.44 20.02
C 20.1 10.44 0 10.19
D 30 20.02 10.19 0

> Now, if I start from C, I get C->D->B->A

I don't. The stages I get are:

V' = {C} E' = {}
V' = {C, D} E' = {(C, D)}
V' = {C, D, B} E' = {(C, D), (C, B)}
V' = {C, D, B, A} E' = {(C, D), (C, B), (B, A)}

> But if I start from B, I get B->A->C->D.

No, I get:

V' = {B} E' = {}
V' = {B, A} E' = {(B, A)}
V' = {B, A, C} E' = {(B, A), (B, C)}
V' = {B, A, C, D} E' = {(B, A), (B, C), (C, D)}

> These are two different trees?

The two I get are the same. I can't tell what you are doing wrong.

> Guess they would be equivalent if you closed the loop:
> C->D->B->A->C
> B->A->C->D->B
> In which case, I think the usual proofs of correctness would be
> correct.

Then they would not be trees! A tree has no loops.

--
Ben.
 | 
Pages: 1
Prev: Processing Emails Online!Earns $1000's Weekly!
Next: The strong non circular list argument.