graph (depth-search) question
I got stuck at solving some problem.
We have two cities that are connected with two roads and betwen those two paths/roads we have regional roads. We know the time that is needed to pass certain part of the road. Now I have variable x which means number of road sections.
The diagram for x = 3 would look like:
One section is made of 3 roads: left, right and regional where we know the time that is needed to pass each of them.
|________| first section
|________| second section
| | third section
Now the problem I have to solve is to find the shortest path from City one to City two.
I tried solving the problem using bruteforce (calculating all the possiblities) but in practice this is obviously a very bad solution (it takes a lot of time to calculate the shortest path if we have 1000 sections - there are 2^1000 combinations).
Now I have came across some algorithms for solving that kind of problems (in depth-search).
I managed to write the code that will put all the nodes in an array where each node has two pointers to other nodes (left and right) - for each crossing of the roads.
I have no idea how should I now determine to find the shortest path (and print it).
I know I should keep track of visited nodes, but I have no idea how to implement this?
Any help is highly appreciated!