Chineses Postman problem requires a bit of Djktras Watch

Terabyte
Badges: 0
#1
Report Thread starter 12 years ago
#1
Decision maths.

Hey,
When pairing up the odd verticies of a chinese postman problem. Do you need to use Djktra's alogrithm to find the smallest weighting between them?

In the book they just say find the pairing so that the weighting is minimal..

but that takes ages.. basically applying it 6 times.. (maximum of 3 pairing combinations... but there's two of them!)

Isn't there a quicker way?
0
quote
reply
Convalescent
Badges: 0
Rep:
?
#2
Report 12 years ago
#2
I usually do it by 'inspection' but if you can't do that, then use Dijkstra.
0
quote
reply
Terabyte
Badges: 0
#3
Report Thread starter 12 years ago
#3
ok cool
0
quote
reply
samd
Badges: 10
Rep:
?
#4
Report 12 years ago
#4
(Original post by Terabyte)
ok cool
Yeah given there is a maximum of three odd pairs it doesn't take too long. Consider odd vertices A, B, C, D, E and F.

AB, CD, EF
AB, CE, DF
AB, CF, DE
--
AC, BD, EF
AC, BE, DF
AC, BF, DE
--
AD, BC, EF
AD, CE, BF
AD, CF, BE

etc.

There are fifteen in total.
0
quote
reply
X

Reply to thread

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Sheffield Hallam University
    City Campus Undergraduate
    Thu, 13 Dec '18
  • University of Buckingham
    Open Evening Undergraduate
    Thu, 13 Dec '18
  • University of Lincoln
    Mini Open Day at the Brayford Campus Undergraduate
    Wed, 19 Dec '18

Do you like exams?

Yes (205)
18.69%
No (665)
60.62%
Not really bothered about them (227)
20.69%

Watched Threads

View All