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

迪杰斯特拉(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不能够处理的场景

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

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

• 节点对象定义：
  

1. public class Edge
2.     {
3.         public int StartNodeID;
4.         public int EndNodeID;
5.         public double Weight;
6.     }
7. public class Node
8.     {
9.         public int Id { get; set; }
10.         public bool Enable { get; set; }
11.     }
12. public class NodeItem
13.         {
14.             public bool Used { get; set; }
15.             public List<int> Nodes { get; } = new List<int>();
16.             public int NodeId { get; set; }
17.             public int Index { get; set; }
18.             public double Weight { get; set; }
19.         }

复制代码

• 初始化图，点，路径集合
  

1. public void Initialize(IEnumerable<Edge> edges, IEnumerable<Node> nodes)
2.         {
3.             _edges = edges.ToList();
4.             _nodes = nodes.ToList();
5.             _nodeItems = new List<NodeItem>();
6.             _graph = new double[_nodes.Count(), _nodes.Count()];
7.             foreach (var row in Enumerable.Range(0, _nodes.Count()))
8.             {
9.                 var rowNode = _nodes[row];
10.                 foreach (var colnum in Enumerable.Range(0, _nodes.Count()))
11.                 {
12.                     if (row == colnum)
13.                     {
14.                         _graph[row, colnum] = 0;
15.                         continue;
16.                     }
17.                     var edge = _edges.FirstOrDefault(x =>
18.                             x.StartNodeID == rowNode.Id && x.EndNodeID == _nodes[colnum].Id);
19.                     _graph[row, colnum] = edge == null ? double.MaxValue : edge.Weight;
20.                 }
22.                 _nodeItems.Add(new NodeItem()
23.                 {
24.                     NodeId = _nodes[row].Id,
25.                     Index = row,
26.                     Weight = double.MaxValue
27.                 });
28.             }
29.         }

复制代码

• 路由主体方法
  

1. public Route GetRoute(int startPointID, int endPointID)
2.         {
3.             if (IsRouting)
4.                 throw new InvalidOperationException($"can't route.router busy");
6.             IsRouting = true;
7.             Node sNode = null;
8.             Node dNode = null;
10.             try
11.             {
12.                 if ((sNode = _nodes.FirstOrDefault(x => x.Id == startPointID)) == null
13.                     || (dNode = _nodes.FirstOrDefault(x => x.Id == endPointID)) == null)
14.                     throw new ArgumentNullException("can't found target points.");
16.                 _nodeItems.FirstOrDefault(x => x.NodeId == startPointID).Used = true;
17.                 _nodeItems.ForEach(x =>
18.                 {
19.                     x.Weight = GetRowArray(_graph, _nodes.IndexOf(sNode))[x.Index];
20.                     x.Nodes.Add(startPointID);
21.                 });
23.                 while (_nodeItems.Any(x => !x.Used))
24.                 {
25.                     var item = GetUnUsedAndMinNodeItem();
26.                     if (item == null)
27.                         break;
29.                     item.Used = true;
30.                     var tempRow = GetRowArray(_graph, item.Index);
31.                     foreach (var nodeItem in _nodeItems)
32.                     {
33.                         if (nodeItem.Weight > tempRow[nodeItem.Index] + item.Weight)
34.                         {
35.                             nodeItem.Weight = tempRow[nodeItem.Index] + item.Weight;
36.                             nodeItem.Nodes.Clear();
37.                             nodeItem.Nodes.AddRange(item.Nodes);
38.                             nodeItem.Nodes.Add(item.NodeId);
39.                         }
40.                     }
41.                 }
43.                 var desNodeitem = _nodeItems.FirstOrDefault(x => x.NodeId == endPointID);
44.                 if (desNodeitem.Used && desNodeitem.Weight < double.MaxValue)
45.                 {
46.                     var edges = new List<Edge>();
47.                     foreach (var index in Enumerable.Range(0, desNodeitem.Nodes.Count - 1))
48.                     {
49.                         edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes[index] && x.EndNodeID == desNodeitem.Nodes[index + 1]));
50.                     }
52.                     edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes.Last() && x.EndNodeID == endPointID));
53.                     return new Route()
54.                     {
55.                         Edges = edges
56.                     };
57.                 }
59.                 return null;
60.             }
61.             catch (Exception ex)
62.             {
63.                 _logger.LogError(ex.ToString());
64.                 _logger.LogInformation($"startPoint:{startPointID}-endpoint:{endPointID} route faild.");
65.                 throw;
66.             }
67.             finally
68.             {
69.                 _nodeItems.ForEach(x =>
70.                 {
71.                     x.Used = false;
72.                     x.Nodes.Clear();
73.                 });
75.                 IsRouting = false;
76.             }
77.         }
79.         private NodeItem GetUnUsedAndMinNodeItem()
80.         {
81.             return _nodeItems.Where(x => !x.Used && x.Weight != double.MaxValue).OrderBy(x => x.Weight).FirstOrDefault();
82.         }
84.         private double[] GetRowArray(double[,] source, int row)
85.         {
86.             double[] result = new double[source.GetLength(1)];
87.             foreach (var index in Enumerable.Range(0, result.Length))
88.             {
89.                 result[index] = source[row, index];
90.             }
92.             return result;
93.         }

复制代码

完整代码

1. public class DijkstraRouter    {        private double[,] _graph;        private List _edges;//所有的边        private List _nodes;//所有的节点        private List _nodeItems;        public bool IsRouting { get; set; }        private readonly ILogger _logger;        public DijkstraRouter(ILogger logger)        {            _logger = logger;        }        public Route GetRoute(int startPointID, int endPointID)
2.         {
3.             if (IsRouting)
4.                 throw new InvalidOperationException($"can't route.router busy");
6.             IsRouting = true;
7.             Node sNode = null;
8.             Node dNode = null;
10.             try
11.             {
12.                 if ((sNode = _nodes.FirstOrDefault(x => x.Id == startPointID)) == null
13.                     || (dNode = _nodes.FirstOrDefault(x => x.Id == endPointID)) == null)
14.                     throw new ArgumentNullException("can't found target points.");
16.                 _nodeItems.FirstOrDefault(x => x.NodeId == startPointID).Used = true;
17.                 _nodeItems.ForEach(x =>
18.                 {
19.                     x.Weight = GetRowArray(_graph, _nodes.IndexOf(sNode))[x.Index];
20.                     x.Nodes.Add(startPointID);
21.                 });
23.                 while (_nodeItems.Any(x => !x.Used))
24.                 {
25.                     var item = GetUnUsedAndMinNodeItem();
26.                     if (item == null)
27.                         break;
29.                     item.Used = true;
30.                     var tempRow = GetRowArray(_graph, item.Index);
31.                     foreach (var nodeItem in _nodeItems)
32.                     {
33.                         if (nodeItem.Weight > tempRow[nodeItem.Index] + item.Weight)
34.                         {
35.                             nodeItem.Weight = tempRow[nodeItem.Index] + item.Weight;
36.                             nodeItem.Nodes.Clear();
37.                             nodeItem.Nodes.AddRange(item.Nodes);
38.                             nodeItem.Nodes.Add(item.NodeId);
39.                         }
40.                     }
41.                 }
43.                 var desNodeitem = _nodeItems.FirstOrDefault(x => x.NodeId == endPointID);
44.                 if (desNodeitem.Used && desNodeitem.Weight < double.MaxValue)
45.                 {
46.                     var edges = new List<Edge>();
47.                     foreach (var index in Enumerable.Range(0, desNodeitem.Nodes.Count - 1))
48.                     {
49.                         edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes[index] && x.EndNodeID == desNodeitem.Nodes[index + 1]));
50.                     }
52.                     edges.Add(_edges.FirstOrDefault(x => x.StartNodeID == desNodeitem.Nodes.Last() && x.EndNodeID == endPointID));
53.                     return new Route()
54.                     {
55.                         Edges = edges
56.                     };
57.                 }
59.                 return null;
60.             }
61.             catch (Exception ex)
62.             {
63.                 _logger.LogError(ex.ToString());
64.                 _logger.LogInformation($"startPoint:{startPointID}-endpoint:{endPointID} route faild.");
65.                 throw;
66.             }
67.             finally
68.             {
69.                 _nodeItems.ForEach(x =>
70.                 {
71.                     x.Used = false;
72.                     x.Nodes.Clear();
73.                 });
75.                 IsRouting = false;
76.             }
77.         }
79.         private NodeItem GetUnUsedAndMinNodeItem()
80.         {
81.             return _nodeItems.Where(x => !x.Used && x.Weight != double.MaxValue).OrderBy(x => x.Weight).FirstOrDefault();
82.         }
84.         private double[] GetRowArray(double[,] source, int row)
85.         {
86.             double[] result = new double[source.GetLength(1)];
87.             foreach (var index in Enumerable.Range(0, result.Length))
88.             {
89.                 result[index] = source[row, index];
90.             }
92.             return result;
93.         }        public void Initialize(IEnumerable<Edge> edges, IEnumerable<Node> nodes)
94.         {
95.             _edges = edges.ToList();
96.             _nodes = nodes.ToList();
97.             _nodeItems = new List<NodeItem>();
98.             _graph = new double[_nodes.Count(), _nodes.Count()];
99.             foreach (var row in Enumerable.Range(0, _nodes.Count()))
100.             {
101.                 var rowNode = _nodes[row];
102.                 foreach (var colnum in Enumerable.Range(0, _nodes.Count()))
103.                 {
104.                     if (row == colnum)
105.                     {
106.                         _graph[row, colnum] = 0;
107.                         continue;
108.                     }
109.                     var edge = _edges.FirstOrDefault(x =>
110.                             x.StartNodeID == rowNode.Id && x.EndNodeID == _nodes[colnum].Id);
111.                     _graph[row, colnum] = edge == null ? double.MaxValue : edge.Weight;
112.                 }
114.                 _nodeItems.Add(new NodeItem()
115.                 {
116.                     NodeId = _nodes[row].Id,
117.                     Index = row,
118.                     Weight = double.MaxValue
119.                 });
120.             }
121.         }        public class NodeItem        {            public bool Used { get; set; }            public List Nodes { get; } = new List();            public int NodeId { get; set; }            public int Index { get; set; }            public double Weight { get; set; }        }    }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！