Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework.
I have a task, where a company has to create a route for a given data set. The data set can be input for every operation and in the end, it should print out the optimum route. The conditions are like this:
- Streets can only be directed North-South or East-West, effectively making every angle between 2 streets in 90 degrees.
- The data set includes streets, junctions and places to pick client and where to drop him off, as well as the starting place for the car.
My problem is, that I'm having trouble thinking of the correct data structure way to do this. What came up first from the top of my head was a directional graph. In theory, it should fit perfectly
- Streets are input up front with numeric identificators
- A node represents junction and is represented by the id's of the streets
- An edge between 2 nodes represents a piece of street and has length
- Places of interest are effectively a sub-class of Junction nodes therefore they have distance from the one node to another.
Best route would then be calculated by finding the shortest path from the starting place of the car to the starting place of the client + shortest path from the starting place of the client to the ending place of the client + shortest path from the ending place of the client to the starting place of the car.
Is my thinking in this matter even remotely correct? I am finding this quite difficult to image with any other data structure than a directed graph, but maybe I'm just limiting my options with this thinking.