How do I find the shortest way through a list of connected waypoints?

public class Waypoint
{
    System.Drawing.Point _loc = new System.Drawing.Point();
    public System.Drawing.Point Location { get { return _loc; } }

    List<Waypoint> _connections = new List<Waypoint>();
    public List<Waypoint> Connections { get { return _connections; } }

    public Waypoint() { }

    public Waypoint(i开发者_运维知识库nt x, int y) { _loc = new System.Drawing.Point(x, y); }
}

... is my class of Waypoints.

I need to find the shortest way from Waypoint A to Waypoint B.

The waypoints are inter-connected. (example: X.Connections contains Y so Y.Connections contains X)

When I designed the system, I have had in mind a way to find them... But it doesn't work.

---

What you want is the A* algorithm.

A* is an extension of the Dijkstra's algorithm but uses a heuristic to estimate the distance left to the final destination (like breadth-first-search does). It is the best of both worlds. :)

The Amit's pages are great to learn the whole algorithm but for a smoother introduction check out this link. It took me a while to understand how A* works but the time spent learning it was really worth it in my opinion.

---

You're describing the Shortest path problem.
Wikipedia has a list of algorithms.

---

You can do this most simply by performing a breadth first search from the initial point until the waypoint is reached.