# Chineses Postman problem requires a bit of DjktrasWatch

#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
12 years ago
#2
I usually do it by 'inspection' but if you can't do that, then use Dijkstra.
0
quote
#3
ok cool
0
quote
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
--

etc.

There are fifteen in total.
0
quote
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### University open days

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

### Poll

Join the discussion

#### Do you like exams?

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