graph (depth-search) question

This is a discussion on graph (depth-search) question within the C++ Programming forums, part of the General Programming Boards category; Hello, I got stuck at solving some problem. We have two cities that are connected with two roads and betwen ...

  1. #1
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630

    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!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list search question..
    By transgalactic2 in forum C Programming
    Replies: 12
    Last Post: 10-29-2008, 05:40 PM
  2. exhaustive graph search
    By Cpro in forum C++ Programming
    Replies: 6
    Last Post: 04-20-2008, 12:08 PM
  3. Search question
    By Aerie in forum C Programming
    Replies: 11
    Last Post: 01-01-2005, 08:45 AM
  4. Simple search program
    By colinuk in forum C Programming
    Replies: 6
    Last Post: 12-18-2004, 01:58 AM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21