单向路由算法-白红宇

单向路由算法

阅读量：6976 次

发布时间：2019-06-27

本文共 3255 字，大约阅读时间需要 10 分钟。

物流行业受成本、中转仓、时间等因素的限制，往往需要对货品的路由线路提出很多要求，怎样快速精准的找到这样的线路，并使用计算机语言实现出来？

根据相关行业经验，抽取了以下计算模型，该算法效率不是最高的，但是比Dijkstra、链路向量等专业算法可能更容易理解：

单向路由解递归实现：

///        /// 单向路由算法       /// 
       /// 起点       /// 终点       /// 地图       /// 限制路由距离       /// 
            public static List
     
      
       > GetAllRouteLine(int start, int end, Dictionary

> map, int LIMIT) { //已找到的通路 var result = new List

>(); //类似于深度优先遍历法，回到原点遍历完成 //纵横栈-->未处理的各层节点 var stackstack = new Stack

>(); //纵向栈-->已连通路段 var verstack = new Stack

(); //起点可1步直达的节点列表 var nextNodes = GetNextNodes(start, verstack.ToList(), LIMIT, end, map, result); if (nextNodes != null) { //起点 verstack.Push(start); //起点对应的下一层 stackstack.Push(nextNodes); while (stackstack.Count > 0) { //当前处理层 var horqueue = stackstack.Peek(); //层层压入(待处理的层) while (horqueue.Count > 0) { nextNodes = GetNextNodes(horqueue.Peek(), verstack.ToList(), LIMIT, end, map, result); if (nextNodes != null) { verstack.Push(horqueue.Peek()); stackstack.Push(nextNodes); horqueue = stackstack.Peek(); } else { horqueue.Dequeue(); } } //层层弹出（处理完的层） while (stackstack.Peek().Count == 0) { stackstack.Pop(); verstack.Pop(); if (stackstack.Count==0) { break; } if (stackstack.Peek().Count > 0) { stackstack.Peek().Dequeue(); } } } } return result; }

辅助函数（可增加各种实际限制条件）

///        /// 获取当前点能走通的下一点集合       /// 
       /// 当前点       /// 已走通路段       /// 限制路由距离       /// 终点       /// 地图       /// 已完成线路集合       /// 
            private static Queue
     
       GetNextNodes(int current, List
      
        hadNode, int LIMIT, int end, Dictionary

> map, List

> result) { for (int i = hadNode.Count; i > 0; i--) { Console.Write(hadNode[i-1]+"-->"); } Console.WriteLine(current); if (current==end) { var line = new List

(); for (int i = hadNode.Count; i >0; i--) { line.Add(hadNode[i - 1]); } line.Add(current); result.Add(line); return null; } if (hadNode.Count>=LIMIT||hadNode.Contains(current)) { return null; } var stack = new Queue

(); if (map.ContainsKey(current)) { foreach (var item in map[current]) { if (!hadNode.Contains(item)&&!stack.Contains(item)) { stack.Enqueue(item); } } if (stack.Count>0) { return stack; } } return null; }

调用方法

static void Main1(string[] args)       {           /*                        1                       / \                      2   3                     /   / \                    4   6   7                   /   / \                  5   8   9          */           Console.WriteLine("地图：");           Console.WriteLine("       1");           Console.WriteLine("      / \\");           Console.WriteLine("     2   3");           Console.WriteLine("    /   / \\");           Console.WriteLine("   4   6   7");           Console.WriteLine("  /   / \\");           Console.WriteLine(" 5   8   9");           var list = new Dictionary

>(); list.Add(1, new List

() { 2, 3 }); list.Add(2, new List

() { 4 }); list.Add(3, new List

() { 6, 7 }); list.Add(4, new List

() { 5 }); list.Add(6, new List

() { 8, 9 }); Console.WriteLine("路由过程："); var result = GetAllRouteLine(1, 8, list, 10); Console.WriteLine("找到通路："); foreach (var item in result) { foreach (var s in item) { Console.Write(s + "-->"); } Console.WriteLine(); } Console.ReadLine(); }

运行结果

转载于:https://www.cnblogs.com/lzzhang/p/4835362.html