《以C#实现最短路径算法.docx》由会员分享，可在线阅读，更多相关《以C#实现最短路径算法.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、/边的定义如下：publicclass EdgepublicstringStartNodelD;publicstringEndNodelD;publicdouble Weight; /权值，代价/节点的定义：publicclass Node privatestring iD ;private List edgeList ;/Edge 的集合出边表 public Node (string id )List();#regionreturnthis.iD ;returnthis.edgeList ;publicclass (合出边表 public Node (string id )List();#r
2、egionreturnthis.iD ;returnthis.edgeList ;publicclass (this.iD = id ;this.edgeList = new get public List EdgeListget#endregion propertypublicstring IDGraph public List m_nodeList = null;public Graph() m nodeList = new List () ;/summary/ 猎取图的节点集合 IIIpublicList returnthis.m_nodeList; /publicvoid Init (
3、) *m_nodeList.Add(aNode);/A - B aEdgel.StartNodelD = aNode.ID; aEdgel.Weight = 10; aEdge2 = new Edge(); aEdge2.EndNodelD = nCn;aNode.EdgeList.Add(aEdge2);/A - E合 IIIpublicList returnthis.m_nodeList; /publicvoid Init () *m_nodeList.Add(aNode);/A - B aEdgel.StartNodelD = aNode.ID; aEdgel.Weight = 10;
4、aEdge2 = new Edge(); aEdge2.EndNodelD = nCn;aNode.EdgeList.Add(aEdge2);/A - ENodeListget“/summary/ 初 始 化 拓扑图 /a Node Node aNode = new Node (nAn); Edge aEdgel = new Edge (); aEdgel.EndNodelD = nBn; EdgeaNode.EdgeList.Add(aEdgel);/A - CaEdge2.StartNodelD = aNode.ID; aEdge2.Weight =20;Edge aEdge3 = new
5、 Edge ();aEdge3.StartNodelD = aNode.ID;aEdge3.EndNodelD = nEn;aEdge3.Weight = 30;aNode.EdgeList.Add(aEdge3)；/ BNode *Node bNode = new Node(nBn);m_nodeList.Add(bNode);/B - CEdge bEdgel = new Edge();bEdgel.StartNodelD = bNode.ID;bEdgel.EndNodelD = nCn;bEdgel.Weight = 5;bNode.EdgeList.Add(bEdgel);/B -
6、EEdgebEdge2 = new Edge();bEdge2.StartNodelD = bNode.ID;bEdge2.EndNodelD = nEH;bEdge2.Weight =10;bNode.EdgeList.Add(bEdge2)；/* c Node * Node cNode = new Node(nCn);m_nodeList.Add(cNode);/C - DEdge cEdgel = new Edge();cEdgel.StartNodelD = cNode.ID;cEdgel.EndNodelD = nDn;cEdgel.Weight =30;cNode.EdgeList
7、.Add(cEdgel)；/* d Node * Node dNode = new Node(nDn);m_nodeList.Add(dNode)；/*E Node *Node eNode = new Node(nEn);m_nodeList.Add(eNode);/E - DEdge eEdgel = new Edge();eEdgel.StartNodelD = eNode.ID;eEdgel.EndNodelD = nDn;eEdgel* Weight = 20;eNode *EdgeListAdd(eEdgel);/summary/ PlanCourse缓存从源节点到其它任一节点的最小
8、权值路径(路径表) /publicclass PlanCourse private Hashtable htPassedPath;#region ctorpublic PlanCourse(List nodeList, string originlD) this.htPassedPath = new Hashtable ();Node originNode = null;foreach(Node node in nodeList)if (node.ID = originlD)PassedPath pPath = newPassedPath(node.ID);this.htPassedPath.
9、Add(node.工D,pPath);if (originNode = null)thrownewException (nTheoriginnodeisnotexist ! n) ;this.InitializeWeight(originNode);/summary/ 通过指定节点的边的权值初始化路径表/summary/privatevoici InitializeWeight (Node originNode) if ( (originNode.EdgeList = null) | | (originNode.EdgeList.Count = 0) return;foreach (Edge
10、edge in originNode.EdgeList)PassedPath pPath = thisedge.EndNodelD;if (pPath = null)continue;pPath.PassedIDList.Add(originNode.ID);pPath .Weight = edge .Weight; #endregion/ 猎取指定点的路径表/paramname=nnodeIDnx/param/public PassedPath thisstring nodelDgetreturn(PassedPath)this.htPassedPathnodelD;/summary/从Pl
11、anCourse取出一个当前累积权值最小，并且没有被处理过的节点/summary/privateNodeGetMinWeightRudeNode(PlanCourse planCourse, List nodeListA string originlD)double weight = double.MaxValue;Node destNode =null;foreach (Node node in nodeList)if (node.ID = originlD)continue;PassedPath pPath =planCoursenode.ID;if(pPath.BeProcessed)c
12、ontinue; if (pPath.Weight weight)weight = pPath.Weight;destNode =node;return destNode;while (curNode ! = null)PassedPath curPath =planCoursecurNode.ID;foreach (Edge edge in curNode.EdgeList) PassedPath targetPath = planCourseedge.EndNodelD;double tempWeight = curPath.Weight + edge.Weight;if (tempWei
13、ght targetPath.Weight) targetPath.Weight = tempWeight; targetPath.PassedIDList.Clear();for (int i = 0; i curPath.PassedIDList.Count; i+) targetPath.PassedIDList.Add(curPath.PassedIDListi. ToString(); targetPath.PassedIDList.Add(curNode.ID); /标 志为已处理 planCourse curNode . ID . BeProcessed = true;/猎取下一
14、个未处 理节点 curNode = this .GetMinWeightRudeNode (planCourse, nodeList, originlD); /summary/从PlanCourse表中取出目标节点的PassedPath,这个PassedPath即是规划 结 果 /private RoutePlanResult GetResult(PlanCourse planCourse, string destID) PassedPath pPath = planCoursedestID;if (pPath.Weight = int.MaxValue)RoutePlanResuit res
15、ultl = new RoutePlanResult(null,int.MaxValue);return resultl;string passedNodelDs =newstringpPath.PassedIDList.Count;for (int i = 0; i passedNodelDs.Length; i+)passedNodelDsi=pPath.PassedIDListi .ToString ();RoutePlanResult result =new RoutePlanResult(passedNodelDs, pPath.Weight);return result;publicclass RoutePlanResult public RoutePlanResult(string passedNodes, double value)m_resultNodes = passedNodes;m_value =value; privatestring m_resultNodes; IIIsummary/ 最短路径经过的节点/publicstring ResultNodesget returnm_resultNodes; privatedouble m_value; / 最短路 径的值/privatedouble Valueget return m value;