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
This is a discussion on need some help in finding the shortest distance within the C Programming forums, part of the General Programming Boards category; 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 ...
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
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.
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
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
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 09: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
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
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
You will need to compute the 'cost' for all paths from O to D. Find the path with the least cost.