路径规划(最短路径)算法C_实现

路径规划（最短路径）算法C#实现路径规划（最短路径）算法C#实现以前空闲的时候用C#实现的路径规划算法，今日贴它出来，看大家有没有更好的实现方案。关于路径规划（最短路径）算法的背景知识，大家可以参考《C++算法－－图算法》一书。该图算法描述的是这样的场景：图由节点和带有方向的边构成，每条边都有相应的权值，路径规划（最短路径）算法就是要找出从节点A到节点B的累积权值最小的路径。首先，我们可以将“有向边”抽象为Edge类：publicclassEdge{publicstringStartNodeID;publicstringEndNodeID;publicdoubleWeight;//权值，代价}节点则抽象成Node类，一个节点上挂着以此节点作为起点的“出边”表。publicclassNode{privatestringiD;privateArrayListedgeList;//Edge的集合－－出边表publicNode(stringid){this.iD=id;this.edgeList=newArrayList();}property#regionpropertypublicstringID{get{returnthis.iD;}}publicArrayListEdgeList{get{returnthis.edgeList;}}#endregion}在计算的过程中，我们需要记录到达每一个节点权值最小的路径，这个抽象可以用PassedPath类来表示：///<summary>///PassedPath用于缓存计算过程中的到达某个节点的权值最小的路径///</summary>publicclassPassedPath{privatestringcurNodeID;privateboolbeProcessed;//是否已被处理privatedoubleweight;//累积的权值privateArrayListpassedIDList;//路径publicPassedPath(stringID){this.curNodeID=ID;this.weight=double.MaxValue;this.passedIDList=newArrayList();this.beProcessed=false;}#regionpropertypublicboolBeProcessed{get{returnthis.beProcessed;}set{this.beProcessed=value;}}publicstringCurNodeID{get{returnthis.curNodeID;}}publicdoubleWeight{get{returnthis.weight;}set{this.weight=value;}}publicArrayListPassedIDList{get{returnthis.passedIDList;}}#endregion}另外，还需要一个表PlanCourse来记录规划的中间结果，即它管理了每一个节点的PassedPath。///<summary>///PlanCourse缓存从源节点到其它任一节点的最小权值路径＝》路径表///</summary>publicclassPlanCourse{privateHashtablehtPassedPath;#regionctorpublicPlanCourse(ArrayListnodeList,stringoriginID){this.htPassedPath=newHashtable();NodeoriginNode=null;foreach(NodenodeinnodeList){if(node.ID==originID){originNode=node;}else{PassedPathpPath=newPassedPath(node.ID);this.htPassedPath.Add(node.ID,pPath);}}if(originNode==null){thrownewException(Theoriginnodeisnotexist!);}this.InitializeWeight(originNode);}privatevoidInitializeWeight(NodeoriginNode){if((originNode.EdgeList==null)||(originNode.EdgeList.Count==0)){return;}foreach(EdgeedgeinoriginNode.EdgeList){PassedPathpPath=this[edge.EndNodeID];if(pPath==null){continue;}pPath.PassedIDList.Add(originNode.ID);pPath.Weight=edge.Weight;}}#endregionpublicPassedPaththis[stringnodeID]{get{return(PassedPath)this.htPassedPath[nodeID];}}}在所有的基础构建好后，路径规划算法就很容易实施了，该算法主要步骤如下：(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的边的权，否则设为double.MaxValue。(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理。(3)重复(2)，直至所有的可达节点都被处理一遍。(4)从PlanCourse表中获取目的点的PassedPath，即为结果。下面就来看上述步骤的实现，该实现被封装在RoutePlanner类中：///<summary>///RoutePlanner提供图算法中常用的路径规划功能。///2005.09.06///</summary>publicclassRoutePlanner{publicRoutePlanner(){}#regionPaln//获取权值最小的路径publicRoutePlanResultPaln(ArrayListnodeList,stringoriginID,stringdestID){PlanCourseplanCourse=newPlanCourse(nodeList,originID);NodecurNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);#region计算过程while(curNode!=null){PassedPathcurPath=planCourse[curNode.ID];foreach(EdgeedgeincurNode.EdgeList){PassedPathtargetPath=planCourse[edge.EndNodeID];doubletempWeight=curPath.Weight+edge.Weight;if(tempWeight<targetPath.Weight){targetPath.Weight=tempWeight;targetPath.PassedIDList.Clear();for(inti=0;i<curPath.PassedIDList.Count;i++){targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());}targetPath.PassedIDList.Add(curNode.ID);}}//标志为已处理planCourse[curNode.ID].BeProcessed=true;//获取下一个未处理节点curNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);}#endregion//表示规划结束returnthis.GetResult(planCourse,destID);}#endregion#regionprivatemethod#regionGetResult//从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果privateRoutePlanResultGetResult(PlanCourseplanCourse,stringdestID){PassedPathpPath=planCourse[destID];if(pPath.Weight==int.MaxValue){RoutePlanResultresult1=newRoutePlanResult(null,int.MaxValue);returnresult1;}string[]passedNodeIDs=newstring[pPath.PassedIDList.Count];for(inti=0;i<passedNodeIDs.Length;i++){passedNodeIDs[i]=pPath.PassedIDList[i].ToString();}RoutePlanResultresult=newRoutePlanResult(passedNodeIDs,pPath.Weight);returnresult;}#endregion#regionGetMinWeightRudeNode//从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点privateNodeGetMinWeightRudeNode(PlanCourseplanCourse,ArrayListnodeList,stringoriginID){doubleweight=double.MaxValue;NodedestNode=null;foreach(NodenodeinnodeList){if(node.ID==originID){continue;}PassedPathpPath=planCourse[node.ID];if(pPath.BeProcessed){continue;}if(pPath.Weight<weight){weight=pPath.Weight;destNode=node;}}returndestNode;}#endregion#endregion}2006.05.22应众多朋友要求，下面给出一个简单示例：RoutePlanner.Plan过程详解：(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的边的权，否则设为double.MaxValue(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理(3)重复(2)，直至所有的可达节点都被处理一遍。(4)从PlanCourse表中获取目的点的PassedPath，即为结果。[STAThread]staticvoidMain(string[]args){ArrayListnodeList=newArrayList();//*****************BNode*******************NodeaNode=newNode(A);nodeList.Add(aNode);//A->BEdgeaEdge1=newEdge();aEdge1.StartNodeID=aNode.ID;aEdge1.EndNodeID=B;aEdge1