Turn on thread page Beta
    • Thread Starter
    Offline

    15
    ReputationRep:


    Hi, need some help on the following questions:

    a)i) Use Dijkstra's algorithm to find the shortest distance from A to J
    I did that with no problems, answer was 27 miles

    ii) A new road is built connecting F to I. The length of this road is x miles, where x is an integer. A shorter route from A to J than that in part bi) is now available. Find the maximum value of x (2 marks)

    And one more question:



    a) List the routes, and their lengths, from B to E, in terms of x where appropriate.

    BAE = 13 mins
    BE = 2x-1 mins
    BCDE = 11 + x mins

    b) On a particular day, it is known that x = 10

    Find the length of an optimal Chinese Postman route on this day, state a possible route corresponding to this minimum length.

    I got BAEDCBEB = 72 mins

    c) Find, no matter what the value of x, which of the three routes should not be used if the total length of a Chinese Postman route is to be optimal. (5 marks)


    Thanks
    • Thread Starter
    Offline

    15
    ReputationRep:
    *bump*
    Offline

    3
    ReputationRep:
    Well, what have you tried so far?
    • Thread Starter
    Offline

    15
    ReputationRep:
    (Original post by ElMoro)
    Well, what have you tried so far?
    For the first one i know x < 27, but i don't know how to figure it out, for the second one i have no clue
    • Thread Starter
    Offline

    15
    ReputationRep:
    *bump*
    Offline

    6
    ReputationRep:
    (Original post by EternalDoom)
    ...
    Just worked through the first question.

    Got 26 miles for a(i). Used route ADCFGHJ. Have checked twice but my diagram is messy so could be wrong.

    For a(ii) my "permanent label" at F is 15C, so using the new edge, FI:
    15+x+5<26
    20+x<26
    x<6

    Hope that helps a little. Not sure if I have time to look through the second question.
    Offline

    3
    ReputationRep:
    (Original post by ecraven)
    For a(ii) my "permanent label" at F is 15C, so using the new edge, FI:
    15+x+5<26
    20+x<26
    x<6
    Alternatively, you can do this.

    Assume that somehow we end up at F (because we're using the line FI) so the shortest way from F to J using FI (which is FIJ and has length x+5) must be shorter than the way without using FI (which is FGHJ which has length 1+6+4=11)
    So, x+5<11
    x<6

    It's essentially the same as what ecraven has done but I thought I'd mention anyway.

    Will get back to you on the second one when I have time. :wink2:
    • Thread Starter
    Offline

    15
    ReputationRep:
    Thanks a bunch, i understand it now, sounds kinda simple now that you think about it, and lemme know when you guys have figured out how to do the second one, and thanks again
    • Thread Starter
    Offline

    15
    ReputationRep:
    *bump* any tips on the last question? D:
    Offline

    3
    ReputationRep:
    (Original post by EternalDoom)
    *bump* any tips on the last question? D:
    Sorry, I haven't looked at it yet. I've been quite busy and haven't done D1 in a while but I will get back to you when I can. :wink2:
    • Thread Starter
    Offline

    15
    ReputationRep:
    (Original post by ElMoro)
    Sorry, I haven't looked at it yet. I've been quite busy and haven't done D1 in a while but I will get back to you when I can. :wink2:
    okies
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: March 28, 2011

University open days

  1. Loughborough University
    General Open Day Undergraduate
    Fri, 21 Sep '18
  2. University of Cambridge
    Churchill College Undergraduate
    Fri, 21 Sep '18
  3. Richmond, The American International University in London
    Undergraduate Open Day Undergraduate
    Fri, 21 Sep '18
Poll
Which accompaniment is best?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.