Thread: graph (depth-search) question

Hello,

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:

Code:

CITY ONE
|        |
|________|       first section
|        |
|        |
|________|       second section
|        |
|        |       third section
|        |
CITY TWO

One section is made of 3 roads: left, right and regional where we know the time that is needed to pass each of them.

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!