https://www.cnblogs.com/zhuweisky/archive/2005/09/29/246677.html
以前空闲的时候用C#实现的路径规划算法，今日贴它出来，看大家有没有更好的实现方案。关于路径规划（最短路径）算法的背景知识，大家可以参考《C++算法－－图算法》一书。
该图算法描述的是这样的场景：图由节点和带有方向的边构成，每条边都有相应的权值，路径规划（最短路径）算法就是要找出从节点A到节点B的累积权值最小的路径。
首先，我们可以将“有向边”抽象为Edge类：
public classEdge
{
public stringStartNodeID ;
public stringEndNodeID ;
public double Weight ; //权值，代价 }
节点则抽象成Node类，一个节点上挂着以此节点作为起点的“出边”表。
public classNode
{
private stringiD ;
private ArrayList edgeList ;//Edge的集合－－出边表
public Node(stringid )
{
this.iD =id ;
this.edgeList = newArrayList() ;
}
property
}
在计算的过程中，我们需要记录到达每一个节点权值最小的路径，这个抽象可以用PassedPath类来表示：
/// ///PassedPath 用于缓存计算过程中的到达某个节点的权值最小的路径
/// public classPassedPath
{
private stringcurNodeID ;
private bool beProcessed ; //是否已被处理 private double weight ; //累积的权值 private ArrayList passedIDList ; //路径public PassedPath(stringID)
{
this.curNodeID =ID ;
this.weight = double.MaxValue ;
this.passedIDList = newArrayList() ;
this.beProcessed = false;
}
#region propertypublic boolBeProcessed
{
get
{
return this.beProcessed ;
}
set
{
this.beProcessed =value ;
}
}
public stringCurNodeID
{
get
{
return this.curNodeID ;
}
}
public doubleWeight
{
get
{
return this.weight ;
}
set
{
this.weight =value ;
}
}
publicArrayList PassedIDList
{
get
{
return this.passedIDList ;
}
}
#endregion
}
另外，还需要一个表PlanCourse来记录规划的中间结果，即它管理了每一个节点的PassedPath。
/// ///PlanCourse 缓存从源节点到其它任一节点的最小权值路径＝》路径表
/// public classPlanCourse
{
privateHashtable htPassedPath ;
#region ctorpublic PlanCourse(ArrayList nodeList ,stringoriginID)
{
this.htPassedPath = newHashtable() ;
Node originNode
= null;
foreach(Node node innodeList)
{
if(node.ID ==originID)
{
originNode
=node ;
}
else
{
PassedPath pPath
= newPassedPath(node.ID) ;
this.htPassedPath.Add(node.ID ,pPath) ;
}
}
if(originNode == null)
{
throw new Exception("The origin node is not exist !") ;
}
this.InitializeWeight(originNode) ;
}
private voidInitializeWeight(Node originNode)
{
if((originNode.EdgeList == null) ||(originNode.EdgeList.Count == 0))
{
return;
}
foreach(Edge edge inoriginNode.EdgeList)
{
PassedPath pPath
= this[edge.EndNodeID] ;
if(pPath == null)
{
continue;
}
pPath.PassedIDList.Add(originNode.ID) ;
pPath.Weight
=edge.Weight ;
}
}
#endregion
public PassedPath this[stringnodeID]
{
get
{
return (PassedPath)this.htPassedPath[nodeID] ;
}
}
}
在所有的基础构建好后，路径规划算法就很容易实施了，该算法主要步骤如下：
(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的边的权，否则设为double.MaxValue。
(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点 经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理。
(3)重复(2)，直至所有的可达节点都被处理一遍。
(4)从PlanCourse表中获取目的点的PassedPath，即为结果。
下面就来看上述步骤的实现，该实现被封装在RoutePlanner类中：
/// ///RoutePlanner 提供图算法中常用的路径规划功能。
///2005.09.06
/// public classRoutePlanner
{
publicRoutePlanner()
{
}
#region Paln//获取权值最小的路径 public RoutePlanResult Paln(ArrayList nodeList ,string originID ,stringdestID)
{
PlanCourse planCourse
= newPlanCourse(nodeList ,originID) ;
Node curNode
= this.GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;
#region 计算过程while(curNode != null)
{
PassedPath curPath
=planCourse[curNode.ID] ;
foreach(Edge edge incurNode.EdgeList)
{
PassedPath targetPath
=planCourse[edge.EndNodeID] ;
double tempWeight = curPath.Weight +edge.Weight ;
if(tempWeight
{
targetPath.Weight
=tempWeight ;
targetPath.PassedIDList.Clear() ;
for(int i=0 ;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
//表示规划结束 return this.GetResult(planCourse ,destID) ;
}
#endregion
#region private method#region GetResult//从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果 private RoutePlanResult GetResult(PlanCourse planCourse ,stringdestID)
{
PassedPath pPath
=planCourse[destID] ;
if(pPath.Weight == int.MaxValue)
{
RoutePlanResult result1
= new RoutePlanResult(null ,int.MaxValue) ;
returnresult1 ;
}
string[] passedNodeIDs = new string[pPath.PassedIDList.Count] ;
for(int i=0 ;i
{
passedNodeIDs[i]
=pPath.PassedIDList[i].ToString() ;
}
RoutePlanResult result
= newRoutePlanResult(passedNodeIDs ,pPath.Weight) ;
returnresult ;
}
#endregion
#region GetMinWeightRudeNode//从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点 private Node GetMinWeightRudeNode(PlanCourse planCourse ,ArrayList nodeList ,stringoriginID)
{
double weight = double.MaxValue ;
Node destNode
= null;
foreach(Node node innodeList)
{
if(node.ID ==originID)
{
continue;
}
PassedPath pPath
=planCourse[node.ID] ;
if(pPath.BeProcessed)
{
continue;
}
if(pPath.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]
static void Main(string[] args)
{
ArrayList nodeList
= newArrayList() ;
//***************** B Node ******************* Node aNode = new Node("A") ;
nodeList.Add(aNode) ;
//A -> B Edge aEdge1 = newEdge() ;
aEdge1.StartNodeID
=aNode.ID ;
aEdge1.EndNodeID
= "B";
aEdge1.Weight
= 10;
aNode.EdgeList.Add(aEdge1) ;
//A -> C Edge aEdge2 = newEdge() ;
aEdge2.StartNodeID
=aNode.ID ;
aEdge2.EndNodeID
= "C";
aEdge2.Weight
= 20;
aNode.EdgeList.Add(aEdge2) ;
//A -> E Edge aEdge3 = newEdge() ;
aEdge3.StartNodeID
=aNode.ID ;
aEdge3.EndNodeID
= "E";
aEdge3.Weight
= 30;
aNode.EdgeList.Add(aEdge3) ;
//***************** B Node ******************* Node bNode = new Node("B") ;
nodeList.Add(bNode) ;
//B -> C Edge bEdge1 = newEdge() ;
bEdge1.StartNodeID
=bNode.ID ;
bEdge1.EndNodeID
= "C";
bEdge1.Weight
= 5;
bNode.EdgeList.Add(bEdge1) ;
//B -> E Edge bEdge2 = newEdge() ;
bEdge2.StartNodeID
=bNode.ID ;
bEdge2.EndNodeID
= "E";
bEdge2.Weight
= 10;
bNode.EdgeList.Add(bEdge2) ;
//***************** C Node ******************* Node cNode = new Node("C") ;
nodeList.Add(cNode) ;
//C -> D Edge cEdge1 = newEdge() ;
cEdge1.StartNodeID
=cNode.ID ;
cEdge1.EndNodeID
= "D";
cEdge1.Weight
= 30;
cNode.EdgeList.Add(cEdge1) ;
//***************** D Node ******************* Node dNode = new Node("D") ;
nodeList.Add(dNode) ;
//***************** C Node ******************* Node eNode = new Node("E") ;
nodeList.Add(eNode) ;
//C -> D Edge eEdge1 = newEdge() ;
eEdge1.StartNodeID
=eNode.ID ;
eEdge1.EndNodeID
= "D";
eEdge1.Weight
= 20;
eNode.EdgeList.Add(eEdge1) ;
RoutePlanner planner
= newRoutePlanner() ;
RoutePlanResult result
= planner.Paln(nodeList ,"A" ,"D") ;
planner
= null;
}
网友评论