如何通过连接的航路点列表找到最短的路线?

|
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(int x, int y) { _loc = new System.Drawing.Point(x, y); }
}
...是我的Waypoint类。 我需要找到从
Waypoint A
Waypoint B
的最短路程。 航路点是相互连接的。 (示例:
X.Connections
包含
Y
,因此
Y.Connections
包含
X
) 在设计系统时,我曾想过一种找到它们的方法……但这是行不通的。     
已邀请:
您想要的是A *算法。 A *是Dijkstra算法的扩展,但使用启发式方法来估计到最终目的地的距离(就像广度优先搜索一样)。这是两全其美。 :) Amit的页面非常适合学习整个算法,但是要获得更流畅的介绍,请查看此链接。我花了一段时间才了解A *的工作原理,但是我认为花时间学习它确实是值得的。     
您正在描述最短路径问题。 维基百科上有一系列算法。     
您可以最简单地执行此操作,方法是从初始点到到达航路点之前先进行广度优先搜索。     

要回复问题请先登录注册