Thread: need some help in finding the shortest distance

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    33

    need some help in finding the shortest distance

    ok so lets suppose we have a graph

    0(0,0)
    A(1,1)
    B(3,5)
    G(4,4)
    D(10,10)

    we start the path from O(0,0) and finish at D(10,10)

    how can we find the shortest distance that we have to do in order to go through 0,A,B,G,D?

    thanks in advance

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Maybe think about how to represent the graph as a data structure in memory.

    Perhaps do some reading on "shortest path" algorithms.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Assuming a straight line, there is only one way to get from one point on a graph to another. The concept of "shortest path" here is a "red herring".
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    i have read many articles on shortest path but i just cant solve this....

    can anyone?

    also say that the distance between two points is d=((Χ2-Χ1)^2+
    (Υ2-Υ1)^2)^1/2

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by jackhasf View Post
    i have read many articles on shortest path but i just cant solve this....

    can anyone?
    Well, you could take care of all the possibilities and choose the lowest total. Even simpler: always pick the closest unvisited point? The more I think about it, the more I am convinced that will be it, altho I can't give you a formula to prove it. Think of a race -- only a fool would do anything but proceed to the nearest goal. Simple, straightforward.
    Last edited by MK27; 02-14-2009 at 10:40 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by MK27 View Post
    Well, you could take care of all the possibilities and choose the lowest total. Even simpler: always pick the closest unvisited point?
    and what if the points are more than the ones i just gave you? If they are 10000? How would i do that?

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by jackhasf View Post
    and what if the points are more than the ones i just gave you? If they are 10000? How would i do that?
    10000 sounds like a lot but that's what computers were invented for.

    Again, always pick the closest (unvisited) one. Use a function that will compute the distance to all remaining points, eliminate the current one from an array, and proceed.

    I imagine there is some genius method out there for precomputing sets of proximate points so that you don't have to repeatedly calculate distances. Look around. If you don't find any reference to such a method, assume oodles of people tried already before realizing that is really is as simple as it sounds.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by MK27 View Post
    Again, always pick the closest (unvisited) one. Use a function that will compute the distance to all remaining points, eliminate the current one from an array, and proceed.
    BTW, this is called Dijkstra's algorithm; you can find a fairly good explanation at http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. Unfortunately, it doesn't tell you much about its efficiency except for its asymptotic runtime. Without going into too much detail (read this book), let me say that Dijkstra is optimal for solving single-source shortest path problems with respect to graphs with non-negative edge-weights.

    Greets,
    Philip

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    You will need to compute the 'cost' for all paths from O to D. Find the path with the least cost.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help finding a simple 'shortest path' algorithm
    By ashley in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 12:38 PM
  2. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  3. Distance Formula in my program..... I need help fast!!!
    By Mackology101 in forum C Programming
    Replies: 3
    Last Post: 09-23-2004, 10:10 PM
  4. Fuzzy Logic
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 10-13-2002, 04:58 PM
  5. using strlen and finding shortest and longest words
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 09-30-2001, 06:09 PM