C#实现最短路径算法

 创建点集

            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
                }
                else
                    currentNode = 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
                }
                else
                    currentNode = 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));
        }
}

原文地址：https://blog.csdn.net/qq996980215/article/details/140389912

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！