C#實現路徑規劃（最短路徑）算法(4)

在所有的基礎構建好後，路徑規劃 算法就很容易實施了，該算法主要步驟如下：

(1)用一張表(PlanCourse) 記錄源點到任何其它一節點的最小權值，初始化這張表時，如果源點能直通某節 點，則權值設為對應的邊的權，否則設為double.MaxValue。

(2)選取沒 有被處理並且當前累積權值最小的節點TargetNode，用其邊的可達性來更新到達 其它節點的路徑和權值（如果其它節點　經此節點後權值變小則更新，否則不更 新），然後標記TargetNode為已處理。

(3)重復(2)，直至所有的可達節 點都被處理一遍。

(4)從PlanCourse表中獲取目的點的PassedPath，即為 結果。

下面就來看上述步驟的實現，該實現被封裝在RoutePlanner類中 ：

Code

[copy to clipboard]

CODE:

/// <summary>
　　/// RoutePlanner 提供圖算法中常用的路徑規劃功 能。
　　/// 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.ToString()) ;
　 　　　　　　　　　　　}
　　　　　　　　　　　　 targetPath.PassedIDList.Add(curNode.ID) ;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　//標志為已處理
　　 　　　　　　planCourse[curNode.ID].BeProcessed = true ;
　　　　 　　　　//獲取下一個未處理節點
　　　　　　　　curNode = this.GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;
　　 　　　　}
　　　　　　#endregion
　　　　　　//表示規劃結束
　　　　　　return this.GetResult(planCourse ,destID) ;　　　　 　　　　
　　　　}
　　　　#endregion
　　　　#region private method
　　　　#region GetResult
　　　　//從 PlanCourse表中取出目標節點的PassedPath，這個PassedPath即是規劃結果
　　　　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 = pPath.PassedIDList.ToString() ;
　　　　　　}
　　　　　　RoutePlanResult result = new RoutePlanResult(passedNodeIDs ,pPath.Weight) ;
　　　　　　return result ;　　　　　　
　　　　}
　　　　#endregion
　　 　　#region GetMinWeightRudeNode
　　　　//從PlanCourse取出一個當 前累積權值最小，並且沒有被處理過的節點
　　　　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
　 　}