当前位置：首页 > news >正文

C#实现最短路径算法

news 来源：原创 2024/9/19 10:01:20

创建点集

            double r = 200 * 500;double width = 1920;double height = 1080;int col = (int)(r / width);int row = (int)(r / height);List<(double, double)> list1 = new List<(double, double)>();for (int i = 0; i < row; ++i){var y = i * height;if (y < r){var xxx = Math.Sqrt(r * r - y * y);var x = xxx - (xxx % width);list1.Add((x, y));list1.Add((-x, y));list1.Add((x, -y));list1.Add((-x, -y));}}

点阵像这样一样

最短路径算法，使用LinkedList返回，后续对插入友好

  LinkedList<(double, double)> NearestNeighborTSP(List<(double, double)> points){int n = points.Count;bool[] visited = new bool[n];visited[0] = true;int current = 0;LinkedList<(double, double)> path = new LinkedList<(double, double)>();path.AddLast(points[current]);for (int i = 1; i < n; i++){double minDistance = double.MaxValue;int next = -1;for (int j = 0; j < n; j++){if (!visited[j]){double dist = Distance(points[current], points[j]);if (dist < minDistance){minDistance = dist;next = j;}}}current = next;visited[current] = true;path.AddLast(points[current]);}path.AddLast(points[0]);return path;}double Distance((double, double) point1, (double, double) point2){return Math.Sqrt(Math.Pow(point1.Item1 - point2.Item1, 2) + Math.Pow(point1.Item2 - point2.Item2, 2));}

路径找完之后（局部展示图，斜线连起来的）

矫正斜线

            var currentNode = res.First;while (currentNode != null && currentNode.Next != null){var nextNode = currentNode.Next;if (currentNode.Value.Item1 != nextNode.Value.Item1 && currentNode.Value.Item2 != nextNode.Value.Item2){var tempX = Math.Min(currentNode.Value.Item1, nextNode.Value.Item1);var tempY = currentNode.Value.Item1 > nextNode.Value.Item1 ? currentNode.Value.Item2 : nextNode.Value.Item2;res.AddAfter(currentNode, (tempX, tempY));currentNode = nextNode; // Skip the inserted node}elsecurrentNode = currentNode.Next;}

矫正后效果

完整测试代码（demo中所用WPF框架,图表控件为ScottPlot5，nuget里直接搜，装5.0以上版本）：

public void test(){double r = 200 * 500;double width = 1920;double height = 1080;int col = (int)(r / width);int row = (int)(r / height);List<(double, double)> list1 = new List<(double, double)>();for (int i = 0; i < row; ++i){var y = i * height;if (y < r){var xxx = Math.Sqrt(r * r - y * y);var x = xxx - (xxx % width);list1.Add((x, y));list1.Add((-x, y));list1.Add((x, -y));list1.Add((-x, -y));}}var wpfPlot = new ScottPlot.WPF.WpfPlot();var xs = list1.Select(x => x.Item1).ToArray();var ys = list1.Select(y => y.Item2).ToArray();var xx = wpfPlot.Plot.Add.Scatter(xs, ys, ScottPlot.Colors.Red).LineWidth = 0;var res = NearestNeighborTSP(list1);var currentNode = res.First;while (currentNode != null && currentNode.Next != null){var nextNode = currentNode.Next;if (currentNode.Value.Item1 != nextNode.Value.Item1 && currentNode.Value.Item2 != nextNode.Value.Item2){var tempX = Math.Min(currentNode.Value.Item1, nextNode.Value.Item1);var tempY = currentNode.Value.Item1 > nextNode.Value.Item1 ? currentNode.Value.Item2 : nextNode.Value.Item2;res.AddAfter(currentNode, (tempX, tempY));currentNode = nextNode; // Skip the inserted node}elsecurrentNode = currentNode.Next;}var xs2 = res.Select(x => x.Item1).ToArray();var ys2 = res.Select(x => x.Item2).ToArray();var yy = wpfPlot.Plot.Add.Scatter(xs2, ys2, ScottPlot.Colors.Blue).LineWidth = 1;grid.Children.Add(wpfPlot);}LinkedList<(double, double)> NearestNeighborTSP(List<(double, double)> points){int n = points.Count;bool[] visited = new bool[n];visited[0] = true;int current = 0;LinkedList<(double, double)> path = new LinkedList<(double, double)>();path.AddLast(points[current]);for (int i = 1; i < n; i++){double minDistance = double.MaxValue;int next = -1;for (int j = 0; j < n; j++){if (!visited[j]){double dist = Distance(points[current], points[j]);if (dist < minDistance){minDistance = dist;next = j;}}}current = next;visited[current] = true;path.AddLast(points[current]);}path.AddLast(points[0]);return path;}double Distance((double, double) point1, (double, double) point2){return Math.Sqrt(Math.Pow(point1.Item1 - point2.Item1, 2) + Math.Pow(point1.Item2 - point2.Item2, 2));}
}