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!

Have you tried searching for "shortest path search"?

I suggest you try that first, then ask more specific problems (that would have been MUCH more efficient than your long post that you've just posted).

[Yes, there are about 1M pages that match this, but the Wikipedia one that comes up first is probably a good starting point].

--
Mats