Mortal Monkey on 25/3/2008 at 15:09

---

Surely Excel allows you to export a few cells to HTML? Just s/\n// before you post. I think it would help us understand what you're working on.

Rug Burn Junky on 25/3/2008 at 18:53

---

I liked this thread better when I thought it said "Sorta Dating Retards."

Thief13x on 26/3/2008 at 05:10

---

Ha, yeah I can definatly empathise. Well, it's been a few semesters since I programmed a working one in Java...I'm not sure how familiar you are with data structures, object oriented programming or the terminology but basically what you need to implement is a Minimum Spanning Tree

(http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf)

those slides contain everything you need to know if you are familiar with object oriented programming and data structures. Basically, here's the rundown

- Your Minimum Spanning Tree consists of Nodes (or towns) which are linked to other nodes through Weighted Edges. These edges are weighted based on the distance. You will have 3 classes...

1) a Tree class containing a vector of node objects as an instance variable

2) a Node class containing a vector of edges objects as its instance variable

3) an Edges class containing a numerical weight as its instance variable

Once you have these classes set up then you need to instantiate a tree object. Your tree class should also have methods to create and add node objects to its vector instance variable. Your node objects should have methods to create and add edge objects to its vector instance variable.

Once you have your tree object, you should use it to create and add the towns which you use to create and add the edges. You're going to be doing this calling methods. Here's how I would right it in java.

Public Static Void Main(String[] args)
{
Tree UnitedStates = new Tree();
Node Dallas = new Node();
Node Seattle = new Node();
Node Pittsburgh = new Node();
Edge Pittsburgh-Dallas = new Edge(1500); (1500 is your distance)
Edge Seattle-Pittsburgh = new Edge (3000);
Edge Seattle-Dallas = new Edge (2500);

Dallas.addRoute(Pittsburgh-Dallas); (addroute will be a method that adds Pittsburgh-Dallas in to the Edge vector instance variable
Pittsburgh.addRoute(Pittsburgh-Dallas);

..etc etc to link all the cities, then, once you have your desired routes set up...

UnitedStates.add(Pittsburgh);
UnitedStates.add(Seattle);
UnitedStates.add(Dallas);


Essentially, you are creating a map, putting towns on the map, and then putting roads linking the towns.

- Once you have this setup, the rest is easy. You simple traverse the tree using a looping greedy algorithm (ie you simply always choose the smallest weight or the shortest road out of your current town) Your loop continues until every town is visited while simultaneously keeping a log of the route it takes. This implies that you must have a way to name your routes, which is appropriate since they are edges and your edges, as well as you nodes will both be instantiations of a edges class (containing an instance variable of its weight) and a node class (containing a vector of links) respectivly


So the traversal would look something like this

Node FINALCHOSENROUTE = new Node(); a node can store a list of the chosen routes in its edges vector instance variable
for (int i = 0; i <= numberOfCities; i++)
{
FINALCHOSENROUTE.add(ShortestRoute.addRoutUnitedStates.city[CurrentCity].chooseShortestRoute()); (chooseShortestRoute will be a method in the Tree class which searches a Node object's vector of Edges for the one with the smallest weight and returns it as an edge)
}

Okay, the final tricky part is CurrentCity must be whatever city the previous chosen route (ie the shortest) led you to. There's a number of ways to do this which will probably involve adding a node instance variable to your edge class. Whenever you create an edge, you will not only have the distance as a parameter but also the destination city. They way, you will simple have to query the edge for its "destination" and plug the return in for your CurrentCity parameter above.

Aight, I got 8am class, hope this helps, if you have any q's or need a hand i'll be more than willing to do what I can for ya.

Cheers

Tim

Thief13x on 27/3/2008 at 00:05

---

woah, thats pretty deep

Chade on 27/3/2008 at 10:09

---

Out of curiosity, how is a minimum spanning tree going to help him optimize the order delivery process?

I am no expert, but I can't see how it is applicable to this problem.