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

Maybe think about how to represent the graph as a data structure in memory.

Perhaps do some reading on "shortest path" algorithms.

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".

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

Quote:

---

Originally Posted by jackhasf

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.

Quote:

---

Originally Posted by MK27

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?

Quote:

---

Originally Posted by jackhasf

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.

Quote:

---

Originally Posted by MK27

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

You will need to compute the 'cost' for all paths from O to D. Find the path with the least cost.