The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Help on a question using Dijkstra's Algorithm (D1) please

I'll take a photo of the question and post it below :smile:
I'm trying to find the minimum weight (which I believe is 43) and then told that the three routes from A to H have the same minimum weight so have to find the values of x and y. I've done this and ended up with a nasty number for x so was wondering if my minmum weight was wrong? My x value is 129/7...
image-af11eefe-61c7-4561-a81c-8b8bacf24e959089410001496203252-compressed.jpg.jpeg

Cheers in advance
Original post by jadonim
I'll take a photo of the question and post it below :smile:
I'm trying to find the minimum weight (which I believe is 43) and then told that the three routes from A to H have the same minimum weight so have to find the values of x and y. I've done this and ended up with a nasty number for x so was wondering if my minmum weight was wrong? My x value is 129/7...
image-af11eefe-61c7-4561-a81c-8b8bacf24e959089410001496203252-compressed.jpg.jpeg

Cheers in advance


Your minimum path is correct, 43.

What equations did you get/use for working out x,y?
Reply 2
Avatar for jadonim
jadonim
OP
12
Original post by ghostwalker
Your minimum path is correct, 43.

What equations did you get/use for working out x,y?


Alright, sweet, cheers...

Attachment not found
(edited 4 years ago)
Original post by jadonim
Alright, sweet, cheers...



Getting "Attachment not found".

However, I did briefly see "2x+3y=43" before you edited it.

The shortest distance to E is 22. You want the shortest distance to H, via E, to be 43. So the distance for E to H needs to be 43-22 = 21.

Hence 2x+3y=21 gives you one equation.

Now do similar with G to H, and solve the two simultaneously. You should end up with integer solutions for x,y.
Reply 4
Avatar for jadonim
jadonim
OP
12
Original post by ghostwalker
Getting "Attachment not found".

However, I did briefly see "2x+3y=43" before you edited it.

The shortest distance to E is 22. You want the shortest distance to H, via E, to be 43. So the distance for E to H needs to be 43-22 = 21.

Hence 2x+3y=21 gives you one equation.

Now do similar with G to H, and solve the two simultaneously. You should end up with integer solutions for x,y.


Ahhhh, yes that makes a lot of sense. Sadly I couldn't seem to find any questions with answers similar to this, but now you've explained it I see where I was going wrong... Right, cheers, much appreciated :smile:

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you