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

C#实现路径规划（最短路径）算法2010-12-19以前空闲的时候用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
   }