以前空閑的時候用C#實現(xiàn)的路徑規(guī)劃算法，今日貼它出來，看大家有沒有更好的實現(xiàn)方案。關于路徑規(guī)劃（最短路徑）算法的背景知識，大家可以參考《C++算法－－圖算法》一書。
該圖算法描述的是這樣的場景：圖由節(jié)點和帶有方向的邊構成，每條邊都有相應的權值，路徑規(guī)劃（最短路徑）算法就是要找出從節(jié)點A到節(jié)點B的累積權值最小的路徑。
首先，我們可以將“有向邊”抽象為Edge類：
public class Edge
{
public string StartNodeID ;
public string EndNodeID ;
public double Weight ; //權值，代價
}
節(jié)點則抽象成Node類，一個節(jié)點上掛著以此節(jié)點作為起點的“出邊”表。
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
}
在計算的過程中，我們需要記錄到達每一個節(jié)點權值最小的路徑，這個抽象可以用PassedPath類來表示：
/// <summary>
/// PassedPath 用于緩存計算過程中的到達某個節(jié)點的權值最小的路徑
/// </summary>
public class PassedPath
{
private string curNodeID ;
private bool beProcessed ; //是否已被處理
private double weight ; //累積的權值
private ArrayList passedIDList ; //路徑
public PassedPath(string ID)
{
this.curNodeID = ID ;
this.weight = double.MaxValue ;
this.passedIDList = new ArrayList() ;
this.beProcessed = false ;
}
#region property
public bool BeProcessed
{
get
{
return this.beProcessed ;
}
set
{
this.beProcessed = value ;
}
}
public string CurNodeID
{
get
{
return this.curNodeID ;
}
}
public double Weight
{
get
{
return this.weight ;
}
set
{
this.weight = value ;
}
}
public ArrayList PassedIDList
{
get
{
return this.passedIDList ;
}
}
#endregion
}
另外，還需要一個表PlanCourse來記錄規(guī)劃的中間結果，即它管理了每一個節(jié)點的PassedPath。
/// <summary>
/// PlanCourse 緩存從源節(jié)點到其它任一節(jié)點的最小權值路徑＝》路徑表
/// </summary>
public class PlanCourse
{
private Hashtable htPassedPath ;
#region ctor
public PlanCourse(ArrayList nodeList ,string originID)
{
this.htPassedPath = new Hashtable() ;
Node originNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
originNode = node ;
}
else
{
PassedPath pPath = new PassedPath(node.ID) ;
this.htPassedPath.Add(node.ID ,pPath) ;
}
}
if(originNode == null)
{
throw new Exception("The origin node is not exist !") ;
}
this.InitializeWeight(originNode) ;
}
private void InitializeWeight(Node originNode)
{
if((originNode.EdgeList == null) ||(originNode.EdgeList.Count == 0))
{
return ;
}
foreach(Edge edge in originNode.EdgeList)
{
PassedPath pPath = this[edge.EndNodeID] ;
if(pPath == null)
{
continue ;
}
pPath.PassedIDList.Add(originNode.ID) ;
pPath.Weight = edge.Weight ;
}
}
#endregion
public PassedPath this[string nodeID]
{
get
{
return (PassedPath)this.htPassedPath[nodeID] ;
}
}
}
在所有的基礎構建好后，路徑規(guī)劃算法就很容易實施了，該算法主要步驟如下：
(1)用一張表(PlanCourse)記錄源點到任何其它一節(jié)點的最小權值，初始化這張表時，如果源點能直通某節(jié)點，則權值設為對應的邊的權，否則設為double.MaxValue。
(2)選取沒有被處理并且當前累積權值最小的節(jié)點TargetNode，用其邊的可達性來更新到達其它節(jié)點的路徑和權值（如果其它節(jié)點 經此節(jié)點后權值變小則更新，否則不更新），然后標記TargetNode為已處理。
(3)重復(2)，直至所有的可達節(jié)點都被處理一遍。
(4)從PlanCourse表中獲取目的點的PassedPath，即為結果。
下面就來看上述步驟的實現(xiàn)，該實現(xiàn)被封裝在RoutePlanner類中：
/// <summary>
/// RoutePlanner 提供圖算法中常用的路徑規(guī)劃功能。
/// 2005.09.06
/// </summary>
public class RoutePlanner
{
public RoutePlanner()
{
}
#region Paln
//獲取權值最小的路徑
public RoutePlanResult Paln(ArrayList nodeList ,string originID ,string destID)
{
PlanCourse planCourse = new PlanCourse(nodeList ,originID) ;
Node curNode = this.GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;
#region 計算過程
while(curNode != null)
{
PassedPath curPath = planCourse[curNode.ID] ;
foreach(Edge edge in curNode.EdgeList)
{
PassedPath targetPath = planCourse[edge.EndNodeID] ;
double tempWeight = curPath.Weight + edge.Weight ;
if(tempWeight < targetPath.Weight)
{
targetPath.Weight = tempWeight ;
targetPath.PassedIDList.Clear() ;
for(int i=0 ;i<curPath.PassedIDList.Count ;i++)
{
targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString()) ;
}
targetPath.PassedIDList.Add(curNode.ID) ;
}
}
//標志為已處理
planCourse[curNode.ID].BeProcessed = true ;
//獲取下一個未處理節(jié)點
curNode = this.GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;
}
#endregion
//表示規(guī)劃結束
return this.GetResult(planCourse ,destID) ;
}
#endregion
#region private method
#region GetResult
//從PlanCourse表中取出目標節(jié)點的PassedPath，這個PassedPath即是規(guī)劃結果
private RoutePlanResult GetResult(PlanCourse planCourse ,string destID)
{
PassedPath pPath = planCourse[destID] ;
if(pPath.Weight == int.MaxValue)
{
RoutePlanResult result1 = new RoutePlanResult(null ,int.MaxValue) ;
return result1 ;
}
string[] passedNodeIDs = new string[pPath.PassedIDList.Count] ;
for(int i=0 ;i<passedNodeIDs.Length ;i++)
{
passedNodeIDs[i] = pPath.PassedIDList[i].ToString() ;
}
RoutePlanResult result = new RoutePlanResult(passedNodeIDs ,pPath.Weight) ;
return result ;
}
#endregion
#region GetMinWeightRudeNode
//從PlanCourse取出一個當前累積權值最小，并且沒有被處理過的節(jié)點
private Node GetMinWeightRudeNode(PlanCourse planCourse ,ArrayList nodeList ,string originID)
{
double weight = double.MaxValue ;
Node destNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
continue ;
}
PassedPath pPath = planCourse[node.ID] ;
if(pPath.BeProcessed)
{
continue ;
}
if(pPath.Weight < weight)
{
weight = pPath.Weight ;
destNode = node ;
}
}
return destNode ;
}
#endregion
#endregion
}
