以C#实现最短路径算法

//边的定义如下：publicclassEdge(publicstringStartNodelD;publicstringEndNodelD;publicdoubleWeight;//权值，代价}//节点的定义：publicclassNode(privatestringiD;privateList<Edge>edgeList;//Edge的集合 出边表publicNode(stringid)(this.iD=id;this.edgeList=newList<Edge>();}#regionpropertypublicstringID(get(returnthis.iD;}}publicList<Edge>EdgeList(get(returnthis.edgeList;}}#endregion本次用于分析的拓扑图如下：（A为起点，D为终点，边上的数字为权值）利用上述的边与节点的定沁.可以通过代码简单的构成如下囹:publicclassGraph(publicList<Node>m_nodeList=null;publicGraph()(m_nodeListnewList<Node>();}///<summary>///获取图的节点集合///</summary>publicList<Node>NodeList(get{returnthis.m_nodeList;}}///<summary>///初始化拓扑图///</summary>publicvoidInit(){//****mm*ANode*******************//****mm*ANode*******************NodeaNodenewNode("A");m_nodeList.Add(aNode);//A->BEdgeaEdgelnewEdge();aEdgel.StartNodelD=aNode.ID;aEdgel.EndNodelD"B";aEdgel.Weight10;aNode.EdgeList.Add(aEdgel);//A->CEdgeaEdge2newEdge();aEdge2.StartNodeID=aNode.ID;aEdge2.EndNodeID"C";aEdge2.Weight20;aNode.EdgeList.Add(aEdge2);//A->EEdgeaEdge3newEdge();aEdge3.StartNodeID=aNode.ID;aEdge3.EndNodeID"E";aEdge3.Weight30;aNode.EdgeList.Add(aEdge3);//*****mmBNode*******************NodebNodenewNode("B");m_nodeList.Add(bNode);//B->CEdgebEdgelnewEdge();bEdgel.StartNodeID=bNode.ID;bEdgel.EndNodeID"C";bEdgel.Weight5;bNode.EdgeList.Add(bEdgel);//B->EEdgebEdge2newEdge();bEdge2.StartNodeID=bNode.ID;bEdge2.EndNodeID"E";bEdge2.Weight10;bNode.EdgeList.Add(bEdge2);//*****************cNode*******************NodecNodenewNode("C");m_nodeList.Add(cNode);//C->DEdgecEdgelnewEdge();cEdgel.StartNodeID=cNode.ID;cEdgel.EndNodeID"D";cEdgel.Weight30;cNode.EdgeList.Add(cEdgel);*****************DNode*******************NodedNodenewNode("D");m_nodeList.Add(dNode);//*****************eNode*******************NodeeNodenewNode("E");m^odeList.Add(eNode);//定->DEdgeeEdgelnewEdge();eEdgel.StartNodelD=eNode.ID;eEdgel.EndNodelD"D";eEdgel.Weight=0;eNode.EdgeList.Add(eEdgel);}}有了拓扑节点和边，就可以.根据算法构造其他最短路径分析的对象了，主要步噱如下:>初始化图中的从独发的路径集合：III<s^mmar^'>IIIPlanCourse缓存从源节点到其它任一节点的最小权值路径(路径表)III<Isummary>publicclassPlanCourse(privateHashtablehtPassedPath;#regionctorpublicPlanCourse(List<Node>nodeList,stringoriginlD)(this.htPassedPath=newHashtable();NodeoriginNodenull;foreach(NodenodeinnodeList)(if(node.ID==originlD)(originNode=node;}else(PassedPathpPathnewPassedPath(node.ID);this.htPassedPath.Add(node.ID,pPath);}}if(originNode==null)thrownewException("Theoriginnodeisnotexist!");this.InitializeWeight(originNode);}///<summary>///通过指定节点的边的权值初始化路径表///</summary>///<paramname="originNode"></param>privatevoidInitializeWeight(NodeoriginNode)(if((originNode.EdgeList==null)||(originNode.EdgeList.Count==0))(return;}foreach(EdgeedgeinoriginNode.EdgeList)(PassedPathpPaththis[edge.EndNodeID];if(pPath==null)(continue;}pPath.PassedIDList.Add(originNode.ID);pPath.Weight=edge.Weight;}}#endregion///<summary>///获取指定点的路径表///</summary>///<paramname="nodeID"></param>///<returns></returns>publicPassedPaththis[stringnodeID](get(return(PassedPath)this.htPassedPath[nodeID];}>AU中最短路径集合中找到一个最短的路径点时开始分析///<summary>///从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点///</summary>///<returns></returns>privateNodeGetMinWeightRudeNode(PlanCourseplanCourse,List<Node>nodeList,stringoriginID)(doubleweight=double.MaxValue;NodedestNodenull;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;}>修正从独发至最短路径，并重新选择另一个最短路径点V」点开始分析，重新执行上述步骤的路径分析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].BeProcessedtrue;//获取下一个未处理节点curNode=this.GetMinWeightRudeNode(planCourse,nodeList,originID);}>重复上述两个步骏，一直到所有的对象都分析完为止。>这个时候的路径集合表中已经保存了从蛭H壬意一点的最短路径集合了。///<summary>///从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果///</summary>///<returns></returns>privateRoutePlanResultGetResult(PlanCourseplanCourse,stringdestID)(PassedPathpPath=planCourse[destID];if(pPath.Weight==int.MaxValue)(RoutePlanResultsult1=newRoutePlanResult(null,int.MaxValue);returnresult1;}string[]passedNodeIDs=newstring[pPath.PassedIDList.Count];for(inti=0