以前空闲的时候用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(EdgeedgeinoriginNode.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;
}
相关推荐
最短路径算法最短路径算法最短路径算法最短路径算法
C#实现最短路径算法的简单小例子,希望对研究该算法的朋友有帮助
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
C#最短路径算法源码
C#实现最短路径Dijkstra算法,基于VS2010,控制台应用程序,可直接运行
最短路径算法 实现 FindShortPath C# VC++
最短路径算法 用C#实现,很有条理性,值得研究
这是关于最短路径方面的一个单元最短路径算法,有谁有遗传算法贡献一下下,谢谢了!
这个是关于SPFA最短路径一些相关东西。。
详细讲述如何实现最短路径,及c#的代码实现
本小组项目基于 Dijkstra 算法,以武汉大学范围(文理学部,工学部,信息学部)为例,设计两种模式—地名输入模式和自由选点模式,并根据输入地名或选择点位自动规划出起点与终点间的最短路径在地图上予以显示,同时...
遗传算法最短路径c#实现
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。本实例实现了求最小路径的权值还能绘出最小路径的走法...
含有各种障碍物的,水平面两点间最短的距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是Dijkstra!不是Floyd!
使用C# net4.0实现了Dijkstra算法,可以获取有向图上某一点到其余所有点的最短路径,能输出路径的前驱节点,完整的路径你看了我的程序说明一定能明白怎么输出两点间的路径。 读取 Excel 一定需要电脑上有安装 office...
C# 退火算法 最短路径 C# 退火算法 最短路径 C# 退火算法 最短路径
Dijkstra最短路径算法,C# 语言实现。里面以一个测试实例说明代码的可实现性
C#最短路径使用VS2017,提供源码,计算两地之间的最短距离算法
C#编写的迷宫小程序,可以自动寻找迷宫的出口和入口路径,还可以寻找迷宫的最短路径
C#算法实现(哈希表 图 二叉树 KMP prim 最短路径 各种排序)!希望大家喜欢!