Log in

No account? Create an account
entries friends calendar profile Previous Previous Next Next
shadows of echoes of memories of songs
Oxbridges of Konigsberg
Read 35 | Write
katstevens From: katstevens Date: February 11th, 2009 05:38 pm (UTC) (Link)
Make it into a weighted graph and I can apply an adaptation of Dijkstra's algorithm for you?
j4 From: j4 Date: February 11th, 2009 07:12 pm (UTC) (Link)
Er, um. Can you explain how to make it into a weighted graph?

NB imagine you're explaining it to somebody who didn't do any maths beyond GCSE, because that's precisely what you'll be doing. :-}
caramel_betty From: caramel_betty Date: February 11th, 2009 07:29 pm (UTC) (Link)
A graph is something like this:


So there's a road (edge) from college 6 to college 4, and a road from college 4 to college 5. There's no direct road between 3 and 5, but you can get there going indirectly. A weighted graph is that, with the distance between each college provided as a weight.

So what you're being asked for is basically: "Can you draw me a map with all the allowable cycle routes on, and the distance of each bit?"

Edited at 2009-02-11 07:30 pm (UTC)
katstevens From: katstevens Date: February 11th, 2009 08:17 pm (UTC) (Link)
Beaten to it! That'll teach me to directly reply via email :)
katstevens From: katstevens Date: February 11th, 2009 08:09 pm (UTC) (Link)
Hurray one of the bits of maths that's relatively easy to explain :)

First, make all of the colleges into dots (or nodes).

Second, draw lines between all the dots (or edges) - these represent the possible paths you'd go on your bike between the colleges so if there is more than one way to get between two colleges, you can draw two lines.

Third, put a number (the weight) onto each edge - this number represents the time in minutes (or seconds, whatever) it takes to travel each edge. Obv if you have two edges between the same two nodes, the one with the lowest figure is going to be the one you want if you're trying to do a shortest route thing, and you can get rid of the lengthy ones.

Once you've converted Oxford into this sort of abstract map, you can do lots of horrendous calculations on it! Or better yet, get your computer to do them for you!
From: vatine Date: February 11th, 2009 07:21 pm (UTC) (Link)
That'd give you a spanning tree, not necessarily the "the shortest route touching all points", but a minimum-cost traversal of the spanning tree would probably not be TOO far off an optimal route for whatever cost metric chosen).
katstevens From: katstevens Date: February 11th, 2009 08:15 pm (UTC) (Link)
Well, er, yes. My 'adaptation' would involve looking at said spanning tree and going 'which of these routes has a good pub at the end?'
Read 35 | Write