C#实现路径规划（最短路径）算法

以前空闲的时候用C#实现的路径规划算法，今日贴它出来，看大家有没有更 好的实现方案。关于路径规划（最短路径）算法的背景知识，大家可以参考 《C++算法－－图算法》一书。

该图算法描述的是这样的场景：图由节点 和带有方向的边构成，每条边都有相应的权值，路径规划（最短路径）算法就是 要找出从节点A到节点B的累积权值最小的路径。

首先，我们可以将 “有向边”抽象为Edge类：

Code

[copy to clipboard]

CODE:

public class Edge
　　{
　　　　public string StartNodeID ;
　　　　public string EndNodeID　;
　　　　public double Weight　　　; //权值，代价　　 　　
　　}

节点则抽象成Node类，一个节点上挂着以此节 点作为起点的“出边”表。

Code

[copy to clipboard]

CODE:

public class Node
　　{
　　　　private string iD ;
　　　　private ArrayList edgeList ;//Edge的集合－－出边表
　　　　public Node(string id )
　　 {
　　　　　　this.iD = id ;
　　　　　　this.edgeList = new ArrayList() ;
　　　　}
　　　　property#region property
　　　　public string ID
　　{
　　　　　　get
　　　 　　{
　　　　　　　　return this.iD ;
　　　　　　}
　 　　　}
　　　　public ArrayList EdgeList
　　　{
　　 　　　　get
　　　　　{
　　　　　　　　return this.edgeList ;
　　　　　　}
　　　　}
　　　　#endregion
　 　}