路径规划（最短路径）算法C#实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

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

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

public class Node
}

在计算的过程中，我们需要记录到达每一个节点权值最小的路径，这个抽象可以用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类中：www.elivn.com

    /// <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
    }

     下面给出一个简单示例：
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 ;
        }