路径规划(最短路径)算法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#regionproperty
publicstringID
{
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;
}
#regionproperty
publicboolBeProcessed
{
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;
#regionctor
publicPlanCourse(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(EdgeedgeinoriginN
ode.EdgeList)
{
PassedPathpPath=this[edge.EndNodeID];
if(pPath==null)
{
continue;
}
pPath.PassedIDList.Add(originNode.ID);
pPath.Weight=edge.Weight;
}
}
#endregion
publicPassedPaththis[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->B
EdgeaEdge1=newEdge();
aEdge1.StartNodeID=aNode.ID;
aEdge1.EndNodeID="B";
aEdge1.Weight=10;
aNode.EdgeList.Add(aEdge1);
//A->C
EdgeaEdge2=newEdge();
aEdge2.StartNodeID=aNode.ID;
aEdge2.EndNodeID="C";
aEdge2.Weight=20;
aNode.EdgeList.Add(aEdge2);
//A->E
EdgeaEdge3=newEdge();
aEdge3.StartNodeID=aNode.ID;
aEdge3.EndNodeID="E";
aEdge3.Weight=30;
aNode.EdgeList.Add(aEdge3);
//*****************BNode*******************
NodebNode=newNode("B");
nodeList.Add(bNode);
//B->C
EdgebEdge1=newEdge();
bEdge1.StartNodeID=bNode.ID;
bEdge1.EndNodeID="C";
bEdge1.Weight=5;
bNode.EdgeList.Add(bEdge1);
//B->E
EdgebEdge2=newEdge();
bEdge2.StartNodeID=bNode.ID;
bEdge2.EndNodeID="E";
bEdge2.Weight=10;
bNode.EdgeList.Add(bEdge2);
//*****************CNode*******************
NodecNode=newNode("C");
nodeList.Add(cNode);
//C->D
EdgecEdge1=newEdge();
cEdge1.StartNodeID=cNode.ID;
cEdge1.EndNodeID="D";
cEdge1.Weight=30;
cNode.EdgeList.Add(cEdge1);
//*****************DNode*******************
NodedNode=newNode("D");
nodeList.Add(dNode);
//*****************CNode*******************
NodeeNode=newNode("E");
nodeList.Add(eNode);
//C->D
EdgeeEdge1=newEdge();
eEdge1.StartNodeID=eNode.ID;
eEdge1.EndNodeID="D";
eEdge1.Weight=20;
eNode.EdgeList.Add(eEdge1);
RoutePlannerplanner=newRoutePlanner();
RoutePlanResultresult=planner.Paln(nodeList,"A","D");
planner=null;
}