最短路径算法-迪杰斯特拉(Dijkstra)算法在c#中的实现和生产应用

  • 最短路径算法-迪杰斯特拉(Dijkstra)算法在c#中的实现和生产应用已关闭评论
  • 20 次浏览
  • A+
所属分类:.NET技术
摘要

迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想),直到扩展到终点为止

迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想),直到扩展到终点为止

贪心算法(Greedy Algorithm)

贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好/最优的解。

Dijkstra推导过程(摘自:https://zhuanlan.zhihu.com/p/346558578)

  • 通过Dijkstra计算图G中的最短路径时,需要指定一个起点D(即从顶点D开始计算)。
  • 此外,引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
  • 初始时,数组S中只有起点D;数组U中是除起点D之外的顶点,并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻,距离为无穷大。
  • 然后,从数组U中找出路径最短的顶点K,并将其加入到数组S中;同时,从数组U中移除顶点K。接着,更新数组U中的各顶点到起点D的距离。
  • 重复第4步操作,直到遍历完所有顶点。

图解(摘自:https://zhuanlan.zhihu.com/p/346558578)

最短路径算法-迪杰斯特拉(Dijkstra)算法在c#中的实现和生产应用

当我们理解了算法原理后,我们需要明白Dijkstra不能够处理的场景

  • 不能处理负权重边(往往找错最短路径,在Dijkstra看来,cost是递增的)
  • A-A的绕圈路径查找(需要特殊处理)

代码实战(已经在生产使用)

  • 节点对象定义:
public class Edge     {         public int StartNodeID;         public int EndNodeID;         public double Weight;     } public class Node     {         public int Id { get; set; }         public bool Enable { get; set; }     } public class NodeItem         {             public bool Used { get; set; }             public List<int> Nodes { get; } = new List<int>();             public int NodeId { get; set; }             public int Index { get; set; }             public double Weight { get; set; }         } 
  • 初始化图,点,路径集合
public void Initialize(IEnumerable<Edge> edges, IEnumerable<Node> nodes)         {             _edges = edges.ToList();             _nodes = nodes.ToList();             _nodeItems = new List<NodeItem>();             _graph = new double[_nodes.Count(), _nodes.Count()];             foreach (var row in Enumerable.Range(0, _nodes.Count()))             {                 var rowNode = _nodes[row];                 foreach (var colnum in Enumerable.Range(0, _nodes.Count()))                 {                     if (row == colnum)                     {                         _graph[row, colnum] = 0;                         continue;                     }                     var edge = _edges.FirstOrDefault(x =>                             x.StartNodeID == rowNode.Id && x.EndNodeID == _nodes[colnum].Id);                     _graph[row, colnum] = edge == null ? double.MaxValue : edge.Weight;                 }                  _nodeItems.Add(new NodeItem()                 {                     NodeId = _nodes[row].Id,                     Index = row,                     Weight = double.MaxValue                 });             }         } 
  • 路由主体方法
public Route GetRoute(int startPointID, int endPointID)         {             if (IsRouting)                 throw new InvalidOperationException($"can't route.router busy");              IsRouting = true;             Node sNode = null;             Node dNode = null;              try             {                 if ((sNode = _nodes.FirstOrDefault(x => x.Id == startPointID)) == null                     || (dNode = _nodes.FirstOrDefault(x => x.Id == endPointID)) == null)                     throw new ArgumentNullException("can't found target points.");                  _nodeItems.FirstOrDefault(x => x.NodeId == startPointID).Used = true;                 _nodeItems.ForEach(x =>                 {                     x.Weight = GetRowArray(_graph, _nodes.IndexOf(sNode))[x.Index];                     x.Nodes.Add(startPointID);                 });                  while (_nodeItems.Any(x => !x.Used))                 {                     var item = GetUnUsedAndMinNodeItem();                     if (item == null)                         break;                      item.Used = true;                     var tempRow = GetRowArray(_graph, item.Index);                     foreach (var nodeItem in _nodeItems)                     {                         if (nodeItem.Weight > tempRow[nodeItem.Index] + item.Weight)                          {                             nodeItem.Weight = tempRow[nodeItem.Index] + item.Weight;                             nodeItem.Nodes.Clear();                             nodeItem.Nodes.AddRange(item.Nodes);                             nodeItem.Nodes.Add(item.NodeId);                         }                     }                 }                  var desNodeitem = _nodeItems.FirstOrDefault(x => x.NodeId == endPointID);                 if (desNodeitem.Used && desNodeitem.Weight < double.MaxValue)                 {                     var edges = new List<Edge>();                     foreach (var index in Enumerable.Range(0, desNodeitem.Nodes.Count - 1))                     {                         edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes[index] && x.EndNodeID == desNodeitem.Nodes[index + 1]));                     }                      edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes.Last() && x.EndNodeID == endPointID));                     return new Route()                     {                         Edges = edges                     };                 }                  return null;             }             catch (Exception ex)             {                 _logger.LogError(ex.ToString());                 _logger.LogInformation($"startPoint:{startPointID}-endpoint:{endPointID} route faild.");                 throw;             }             finally             {                 _nodeItems.ForEach(x =>                 {                     x.Used = false;                     x.Nodes.Clear();                 });                  IsRouting = false;             }         }          private NodeItem GetUnUsedAndMinNodeItem()         {             return _nodeItems.Where(x => !x.Used && x.Weight != double.MaxValue).OrderBy(x => x.Weight).FirstOrDefault();         }          private double[] GetRowArray(double[,] source, int row)         {             double[] result = new double[source.GetLength(1)];             foreach (var index in Enumerable.Range(0, result.Length))             {                 result[index] = source[row, index];             }              return result;         } 

完整代码

public class DijkstraRouter     {         private double[,] _graph;         private List<Edge> _edges;//所有的边         private List<Node> _nodes;//所有的节点         private List<NodeItem> _nodeItems;         public bool IsRouting { get; set; }          private readonly ILogger<DijkstraRouter> _logger;          public DijkstraRouter(ILogger<DijkstraRouter> logger)         {             _logger = logger;         }          public Route GetRoute(int startPointID, int endPointID)         {             if (IsRouting)                 throw new InvalidOperationException($"can't route.router busy");              IsRouting = true;             Node sNode = null;             Node dNode = null;              try             {                 if ((sNode = _nodes.FirstOrDefault(x => x.Id == startPointID)) == null                     || (dNode = _nodes.FirstOrDefault(x => x.Id == endPointID)) == null)                     throw new ArgumentNullException("can't found target points.");                  _nodeItems.FirstOrDefault(x => x.NodeId == startPointID).Used = true;                 _nodeItems.ForEach(x =>                 {                     x.Weight = GetRowArray(_graph, _nodes.IndexOf(sNode))[x.Index];                     x.Nodes.Add(startPointID);                 });                  while (_nodeItems.Any(x => !x.Used))                 {                     var item = GetUnUsedAndMinNodeItem();                     if (item == null)                         break;                      item.Used = true;                     var tempRow = GetRowArray(_graph, item.Index);                     foreach (var nodeItem in _nodeItems)                     {                         if (nodeItem.Weight > tempRow[nodeItem.Index] + item.Weight)                          {                             nodeItem.Weight = tempRow[nodeItem.Index] + item.Weight;                             nodeItem.Nodes.Clear();                             nodeItem.Nodes.AddRange(item.Nodes);                             nodeItem.Nodes.Add(item.NodeId);                         }                     }                 }                  var desNodeitem = _nodeItems.FirstOrDefault(x => x.NodeId == endPointID);                 if (desNodeitem.Used && desNodeitem.Weight < double.MaxValue)                 {                     var edges = new List<Edge>();                     foreach (var index in Enumerable.Range(0, desNodeitem.Nodes.Count - 1))                     {                         edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes[index] && x.EndNodeID == desNodeitem.Nodes[index + 1]));                     }                      edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes.Last() && x.EndNodeID == endPointID));                     return new Route()                     {                         Edges = edges                     };                 }                  return null;             }             catch (Exception ex)             {                 _logger.LogError(ex.ToString());                 _logger.LogInformation($"startPoint:{startPointID}-endpoint:{endPointID} route faild.");                 throw;             }             finally             {                 _nodeItems.ForEach(x =>                 {                     x.Used = false;                     x.Nodes.Clear();                 });                  IsRouting = false;             }         }          private NodeItem GetUnUsedAndMinNodeItem()         {             return _nodeItems.Where(x => !x.Used && x.Weight != double.MaxValue).OrderBy(x => x.Weight).FirstOrDefault();         }          private double[] GetRowArray(double[,] source, int row)         {             double[] result = new double[source.GetLength(1)];             foreach (var index in Enumerable.Range(0, result.Length))             {                 result[index] = source[row, index];             }              return result;         }          public void Initialize(IEnumerable<Edge> edges, IEnumerable<Node> nodes)         {             _edges = edges.ToList();             _nodes = nodes.ToList();             _nodeItems = new List<NodeItem>();             _graph = new double[_nodes.Count(), _nodes.Count()];             foreach (var row in Enumerable.Range(0, _nodes.Count()))             {                 var rowNode = _nodes[row];                 foreach (var colnum in Enumerable.Range(0, _nodes.Count()))                 {                     if (row == colnum)                     {                         _graph[row, colnum] = 0;                         continue;                     }                     var edge = _edges.FirstOrDefault(x =>                             x.StartNodeID == rowNode.Id && x.EndNodeID == _nodes[colnum].Id);                     _graph[row, colnum] = edge == null ? double.MaxValue : edge.Weight;                 }                  _nodeItems.Add(new NodeItem()                 {                     NodeId = _nodes[row].Id,                     Index = row,                     Weight = double.MaxValue                 });             }         }          public class NodeItem         {             public bool Used { get; set; }             public List<int> Nodes { get; } = new List<int>();             public int NodeId { get; set; }             public int Index { get; set; }             public double Weight { get; set; }         }     }