带权重的有向图求最短路径

发布日期:2018-02-09    浏览次数:852

  首先新建一个网图如下:

  图的表示法有好多中,最常用的应该是邻接矩阵与邻接表。上面的图,边很少,用邻接表来表示就很不错。

  对于以上图,可以对象出3个类。图、节点、边。3个实体类代码如下:

  边Edge:

    public class Edge
    {
        public string StartNodeID
        {
            get;
            set;
        }
        public string EndNodeID
        {
            get;
            set;
        }
        public int Weight
        {
            get;
            set;
        }
    }

  节点Node:

    public class Node
    {
        private string id;
        private IList<Edge> edgeList;
        public Node(string nid)
        {
            id = nid;
            edgeList = new List<Edge>();
        }

        public string Id
        {
            get
            {
                return id;
            }
        }

        public IList<Edge> EdgeList
        {
            get
            {
                return edgeList;
            }
        }
    }

  图Graph:

    public class Graph
    {
        public List<Node> NodeList = new List<Node>();
    }

  由于要求的就是最短路径,路径对象模拟如下:

    public class Path
    {
        public string CurrentNodeId;
        public bool IsProcessed = false;
        public int Weight = 99999999;
        public List<string> PathNodeList = new List<string>();
    }

  最短路径计算类:

    /// <summary>
    /// 计算最短路径帮助类
    /// </summary>
    public class CaculateHelper
    {
        private Dictionary<string, Path>  dicPath = new Dictionary<string, Path>();
        public Dictionary<string, Path> DicPath
        {
            get
            {
                return dicPath;
            }
        }

        public void IniFirstNode(Graph graph, string StartNodeId)
        {
            Node OriginNode = null;
            foreach (Node node in graph.NodeList)
            {
                if (node.Id == StartNodeId)
                {
                    OriginNode = node;
                }
                else
                {
                    Path path = new Path();
                    path.CurrentNodeId = node.Id;
                    dicPath.Add(path.CurrentNodeId, path);  //初始化A->到所有边都是默认的Path 99999999
                }
            }

            //如果有A直接进入的边,则设置为相应权重值,和记录下路径
            foreach (Edge edge in OriginNode.EdgeList)
            {
                Path path = new Path();
                path.CurrentNodeId = edge.EndNodeID;
                path.Weight = edge.Weight;
                path.PathNodeList.Add(edge.StartNodeID);
                dicPath[path.CurrentNodeId] = path;
            }
        }

        public Node GetFromNodeMinWeightNode(Graph graph)
        {
            Node CNode = null;
            KeyValuePair<string, Path> KVPPath = dicPath.Where(m => !m.Value.IsProcessed).OrderBy(m => m.Value.Weight).FirstOrDefault();
            if (KVPPath.Key != null)
            {
                CNode = graph.NodeList.FirstOrDefault(m => m.Id == KVPPath.Value.CurrentNodeId);
            }
            return CNode;
        }

        /// <summary>
        /// 计算最短权值路径
        /// </summary>
        public void CatelateMinWeightRoad(Graph graph)
        {
            //取从第一个点出发,最小权值且未被访问果的节点的点
            Node CNode = GetFromNodeMinWeightNode(graph);
            //这段代码是核心 循环每个顶点,看看经过该顶点是否会让权值变小,如果会则存起此路径。直到再未访问过的点
            while (CNode != null)
            {
                Path CurrentPath = dicPath[CNode.Id];
                foreach (Edge edge in CNode.EdgeList)
                {
                    Path TargetPath = dicPath[edge.EndNodeID];
                    int tempWeight = CurrentPath.Weight + edge.Weight;
                    if (tempWeight < TargetPath.Weight)
                    {
                        TargetPath.Weight = tempWeight;
                        TargetPath.PathNodeList.Clear();

                        for (int i = 0; i < CurrentPath.PathNodeList.Count; i++)
                        {
                            TargetPath.PathNodeList.Add(CurrentPath.PathNodeList[i].ToString());
                        }

                        TargetPath.PathNodeList.Add(CNode.Id);
                    }
                }

                //标志为已处理
                dicPath[CNode.Id].IsProcessed = true;
                //再次获取权值最小的点
                CNode = GetFromNodeMinWeightNode(graph);
            }
        }
    }

  主控制台程序:

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();

            #region 初始化一个图的 节点和边

            //***************** B Node *******************
            Node aNode = new Node("A");
            graph.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");
            graph.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");
            graph.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");
            graph.NodeList.Add(dNode);

            //***************** C Node *******************
            Node eNode = new Node("E");
            graph.NodeList.Add(eNode);

            //E -> D
            Edge eEdge1 = new Edge();
            eEdge1.StartNodeID = eNode.Id;
            eEdge1.EndNodeID = "D";
            eEdge1.Weight = 20;
            eNode.EdgeList.Add(eEdge1);

            //E -> F
            Edge eEdge2 = new Edge();
            eEdge2.StartNodeID = eNode.Id;
            eEdge2.EndNodeID = "F";
            eEdge2.Weight = 20;
            eNode.EdgeList.Add(eEdge2);

            //***************** F Node *******************
            Node fNode = new Node("F");
            graph.NodeList.Add(fNode);


            #endregion

            //计算从A -> C的最短权值路线
            string StartNodeId = "A";
            string EndNodeId = "F";

            CaculateHelper CH = new CaculateHelper();
            //第一步,初始化初始化源点 A 到 其他各点的 权重以及 路径(完成 A->B A->C A->E A->D 边权重,与A无直接边的则默认99999999)
            CH.IniFirstNode(graph, StartNodeId);
            //第二步,从权重最小的点开始,一直到权值最大的点
            CH.CatelateMinWeightRoad(graph);

            #region 以下与计算无关,仅仅用于将结果打印出来
            Path ShowPath = CH.DicPath[EndNodeId];
            foreach(string MiddleNodeId in ShowPath.PathNodeList)
            {
                Console.WriteLine(MiddleNodeId);
            }
            Console.WriteLine(ShowPath.Weight);
            #endregion

            Console.ReadKey();
        }
    }

  不要小看上面这几行代码,哥看了好久才看懂,如果Node里加几个坐标,就能在地图上面展示了。下一篇会将它改造成可以在地图上面展示的路径规划。

本文网址:https://www.wyxxw.cn/blog-detail-2-6-314.html

返回列表

非特殊说明,本文版权归原作者所有,转载请注明出处

提示:本站所有资源仅供学习与参考,请勿用于商业用途。图片来自互联网~如侵犯您的权益,请联系QQ:1067507709.

提示:转载请注明来自:http://www.cnblogs.com/kissdodog/p/5437897.html 。 转载人:momo