路径规划(最短路径)算法C#实现-阿里云开发者社区

开发者社区> zhuweisky> 正文

路径规划(最短路径)算法C#实现

简介: 以前空闲的时候用C#实现的路径规划算法,今日贴它出来,看大家有没有更好的实现方案。关于路径规划(最短路径)算法的背景知识,大家可以参考《C++算法--图算法》一书。    该图算法描述的是这样的场景:图由节点和带有方向的边构成,每条边都有相应的权值,路径规划(最短路径)算法就是要找出从节点A到节点B的累积权值最小的路径。
+关注继续查看

    以前空闲的时候用C#实现的路径规划算法,今日贴它出来,看大家有没有更好的实现方案。关于路径规划(最短路径)算法的背景知识,大家可以参考《C++算法--图算法》一书。
    该图算法描述的是这样的场景:图由节点和带有方向的边构成,每条边都有相应的权值,路径规划(最短路径)算法就是要找出从节点A到节点B的累积权值最小的路径。
    首先,我们可以将“有向边”抽象为Edge类:

    public class Edge
    {
        
public string StartNodeID ;
        
public string EndNodeID   ;
        
public double Weight      ; //权值,代价        
    }

    节点则抽象成Node类,一个节点上挂着以此节点作为起点的“出边”表。

       public class Node
    
{
        
private string iD ;
        
private ArrayList edgeList ;//Edge的集合--出边表

        
public Node(string id )
     
{
            
this.iD = id ;
            
this.edgeList = new ArrayList() ;
        }


        
property#region property
        
public string ID
     
{
            
get
          
{
                
return this.iD ;
            }

        }


        
public ArrayList EdgeList
      
{
            
get
          
{
                
return this.edgeList ;
            }

        }

        
#endregion

    }

    
    在计算的过程中,我们需要记录到达每一个节点权值最小的路径,这个抽象可以用PassedPath类来表示:

    /// <summary>
    
/// PassedPath 用于缓存计算过程中的到达某个节点的权值最小的路径
    
/// </summary>
    public class PassedPath
    {
        
private string     curNodeID ;
        
private bool     beProcessed ;   //是否已被处理
        private double     weight ;        //累积的权值
        private ArrayList passedIDList ; //路径

        
public PassedPath(string ID)
        {
            
this.curNodeID = ID ;
            
this.weight    = double.MaxValue ;
            
this.passedIDList = new ArrayList() ;
            
this.beProcessed = false ;
        }

        
#region property
        
public bool BeProcessed
        {
            
get
            {
                
return this.beProcessed ;
            }
            
set
            {
                
this.beProcessed = value ;
            }
        }

        
public string CurNodeID
        {
            
get
            {
                
return this.curNodeID ;
            }
        }

        
public double Weight 
        {
            
get
            {
                
return this.weight ;
            }
            
set
            {
                
this.weight = value ;
            }
        }

        
public ArrayList PassedIDList
        {
            
get
            {
                
return this.passedIDList ;
            }
        }
        
#endregion
    }


    另外,还需要一个表PlanCourse来记录规划的中间结果,即它管理了每一个节点的PassedPath。


    
/// <summary>
    
/// PlanCourse 缓存从源节点到其它任一节点的最小权值路径=》路径表
    
/// </summary>
    public class PlanCourse
    {
        
private Hashtable htPassedPath ;    

        
#region ctor
        
public PlanCourse(ArrayList nodeList ,string originID)
        {
            
this.htPassedPath = new Hashtable() ;

            Node originNode 
= null ;
            
foreach(Node node in nodeList)
            {
                
if(node.ID == originID)
                {
                    originNode 
= node ;
                }
                
else
                {
                    PassedPath pPath 
= new PassedPath(node.ID) ;
                    
this.htPassedPath.Add(node.ID ,pPath) ;
                }
            }

            
if(originNode == null
            {
                
throw new Exception("The origin node is not exist !") ;
            }        
    
            
this.InitializeWeight(originNode) ;
        }

        
private void InitializeWeight(Node originNode)
        {
            
if((originNode.EdgeList == null||(originNode.EdgeList.Count == 0))
            {
                
return ;
            }

            
foreach(Edge edge in originNode.EdgeList)
            {
                PassedPath pPath 
= this[edge.EndNodeID] ;
                
if(pPath == null)
                {
                    
continue ;
                }

                pPath.PassedIDList.Add(originNode.ID) ;
                pPath.Weight 
= edge.Weight ;
            }
        }
        
#endregion

        
public PassedPath this[string nodeID]
        {
            
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>
    public class RoutePlanner
    {
        
public RoutePlanner()
        {            
        }

        
#region Paln
        
//获取权值最小的路径
        public RoutePlanResult Paln(ArrayList nodeList ,string originID ,string destID)
        {
            PlanCourse planCourse 
= new PlanCourse(nodeList ,originID) ;

            Node curNode 
= this.GetMinWeightRudeNode(planCourse ,nodeList ,originID) ;

            
#region 计算过程
            
while(curNode != null)
            {
                PassedPath curPath 
= planCourse[curNode.ID] ;
                
foreach(Edge edge in curNode.EdgeList)
                {
                    PassedPath targetPath 
= planCourse[edge.EndNodeID] ;
                    
double tempWeight = curPath.Weight + edge.Weight ;

                    
if(tempWeight < targetPath.Weight)
                    {
                        targetPath.Weight 
= tempWeight ;
                        targetPath.PassedIDList.Clear() ;

                        
for(int i=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
            
            
//表示规划结束
            return this.GetResult(planCourse ,destID) ;                
        }
        
#endregion

        
#region private method
        
#region GetResult
        
//从PlanCourse表中取出目标节点的PassedPath,这个PassedPath即是规划结果
        private RoutePlanResult GetResult(PlanCourse planCourse ,string destID)
        {
            PassedPath pPath 
= planCourse[destID]  ;            

            
if(pPath.Weight == int.MaxValue)
            {
                RoutePlanResult result1 
= new RoutePlanResult(null ,int.MaxValue) ;
                
return result1 ;
            }
            
            
string[] passedNodeIDs = new string[pPath.PassedIDList.Count] ;
            
for(int i=0 ;i<passedNodeIDs.Length ;i++)
            {
                passedNodeIDs[i] 
= pPath.PassedIDList[i].ToString() ;
            }
            RoutePlanResult result 
= new RoutePlanResult(passedNodeIDs ,pPath.Weight) ;

            
return result ;            
        }
        
#endregion

        
#region GetMinWeightRudeNode
        
//从PlanCourse取出一个当前累积权值最小,并且没有被处理过的节点
        private Node GetMinWeightRudeNode(PlanCourse planCourse ,ArrayList nodeList ,string originID)
        {
            
double weight = double.MaxValue ;
            Node destNode 
= null ;

            
foreach(Node node in nodeList)
            {
                
if(node.ID == originID)
                {
                    
continue ;
                }

                PassedPath pPath 
= planCourse[node.ID] ;
                
if(pPath.BeProcessed)
                {
                    
continue ;
                }

                
if(pPath.Weight < weight)
                {
                    weight 
= pPath.Weight ;
                    destNode 
= node ;
                }
            }

            
return destNode ;
        }
        
#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 
= new ArrayList() ;
 
            
//***************** B Node *******************
            Node aNode  = new Node("A") ;
            nodeList.Add(aNode) ;
            
//A -> B
            Edge aEdge1 = new Edge() ;
            aEdge1.StartNodeID 
= aNode.ID ;
            aEdge1.EndNodeID   
= "B" ;
            aEdge1.Weight      
= 10 ;
            aNode.EdgeList.Add(aEdge1) ;
            
//A -> C
            Edge aEdge2 = new Edge() ;
            aEdge2.StartNodeID 
= aNode.ID ;
            aEdge2.EndNodeID   
= "C" ;
            aEdge2.Weight      
= 20 ;
            aNode.EdgeList.Add(aEdge2) ;
            
//A -> E
            Edge aEdge3 = new Edge() ;
            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 = new Edge() ;
            bEdge1.StartNodeID 
= bNode.ID ;
            bEdge1.EndNodeID   
= "C" ;
            bEdge1.Weight      
= 5 ;
            bNode.EdgeList.Add(bEdge1) ;
            
//B -> E
            Edge bEdge2 = new Edge() ;
            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        = new Edge() ;
            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        = new Edge() ;
            eEdge1.StartNodeID 
= eNode.ID ;
            eEdge1.EndNodeID   
= "D" ;
            eEdge1.Weight      
= 20 ;
            eNode.EdgeList.Add(eEdge1) ;


            RoutePlanner planner 
= new RoutePlanner() ;
            RoutePlanResult result 
= planner.Paln(nodeList ,"A" ,"D") ;

            planner 
= null ;
        }



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
算法导论——单元最短路径
  单源最短路径问题是指,给定一个图G=(V,E),希望找到从给定源结点s到每个节点v的最短路径。单源最短路径问题可以用来解决很多最短路径的变体。 单目的地最短路径问题:找到从每个结点v到给定目的地结点t的最短路径。
1591 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
8346 0
消除文法左递归的算法
存储文法的数据结构 1 typedef struct P{ 2 char key; // 产生式左部 3 char * value [16]; // 产生式右部 4 int count; // 几组规则 5 }P...
916 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
11105 0
《图论》——最短路径 Dijkstra算法(戴克斯特拉算法)
十大算法之Dijkstra算法: 最短路径是图论算法中的经典问题。图分为有向图、无向图,路径权值有正值、负值,针对不同的情况需要分别选用不同的算法。在维基上面给出了各种不同的场景应用不同的算法的基本原则:最短路问题。
2679 0
+关注
zhuweisky
从事软件开发行业十多年,专注于网络通信技术和网络语音视频技术,擅长系统架构设计、系统性能优化等。zhuweisky.cnblogs.com
300
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载