C# 根据两点名称，寻找两短路程的最优解，【有数据库设计，完整代码】

前言

如果我们遇到路径问题，可以使用点点连线，给定一个点，可以到达另外几个点，寻找最优解
例：如下图所示，如果要从A1-C1,可以有三条路

1.A1-B1-C1
2.A1-B2-C1
3.A1-B3-C1

最优解肯定是A1-B1-C1，因为两点之间直线最短，但当业务复杂时，我们就要通过轮询来查出最优路径
在这里插入图片描述

数据库设计

首先是数据库的设计：创建表：sys_pilot

CREATE TABLE sys_pilot (
	pilotid numeric(1000) NOT NULL, -- 内场点位Id
	ptname varchar(50) NOT NULL, -- 点位名称
	xaxis int4 NOT NULL, -- X轴
	yaxis int4 NULL, -- Y轴
	transfer varchar(500) NULL, -- 经过点
	CONSTRAINT sys_pilot_pk PRIMARY KEY (pilotid)
);
COMMENT ON TABLE public.sys_pilot IS '点位图表';

后端代码

根据传入的两点名称，例：A1,C1
最优解：A1-B1-C1就会被依次返回

        private static Dictionary<string, Sys_Pilot> _points;
		/// <summary>
        /// 查找图形点位
        /// </summary>
        /// <param name="json"></param>
        /// <returns></returns>
        /// <exception cref="InterfaceException"></exception>
        public List<Sys_Pilot> VerifyPilot(string json)
        {
            Sys_Pilot pilot = JsonHelper.Instance.Deserialize<Sys_Pilot>(json);
            string[] values = pilot.PtName.Split(',');

            if (values.Length != 2)
            {
                throw new InterfaceException("请传入两个点");
            }

            string inPoint = values[0];
            string terminus = values[1];

            List<Sys_Pilot> pilots = _paramsDal.FindData(new Sys_Pilot());


            List<Sys_Pilot> shortestPath = ShortestPath(pilots, inPoint, terminus);

            return shortestPath;
        }
        /// <summary>
        /// 轮询查出中间点
        /// </summary>
        /// <param name="pilots"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        public List<Sys_Pilot> ShortestPath(List<Sys_Pilot> pilots, string start, string end)
        {
            _points = pilots.ToDictionary(p => p.PtName);

            Dictionary<string, int> distances = new Dictionary<string, int>();
            Dictionary<string, string> previous = new Dictionary<string, string>();
            HashSet<string> visited = new HashSet<string>();

            foreach (var point in _points.Values)
            {
                distances[point.PtName] = int.MaxValue;
                previous[point.PtName] = null;
            }

            distances[start] = 0;

            while (visited.Count < _points.Count)
            {
                string current = null;
                int shortestDistance = int.MaxValue;
                foreach (var point in _points.Values)
                {
                    if (!visited.Contains(point.PtName) && distances[point.PtName] < shortestDistance)
                    {
                        current = point.PtName;
                        shortestDistance = distances[point.PtName];
                    }
                }

                visited.Add(current);

                if (current == end)
                    break;

                if (_points[current].Transfer != null) 
                {
                    foreach (var neighbor in _points[current].Transfer.Split(','))
                    {
                        if (!_points.ContainsKey(neighbor))
                            continue;

                        int alt = distances[current] + Distance(_points[current], _points[neighbor]);
                        if (alt < distances[neighbor])
                        {
                            distances[neighbor] = alt;
                            previous[neighbor] = current;
                        }
                    }
                }
                else if (current == end) 
                {
                    break;
                }
            }

            List<Sys_Pilot> path = new List<Sys_Pilot>();
            string temp = end;
            while (temp != null)
            {
                path.Add(_points[temp]);
                temp = previous[temp];
            }
            path.Reverse();
            return path;
        }

        /// <summary>
        /// 计算X,Y轴距离距离
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        private int Distance(Sys_Pilot a, Sys_Pilot b)
        {
            return (int)Math.Sqrt(Math.Pow((a.XAxis - b.XAxis), 2) + Math.Pow((a.YAxis - b.YAxis), 2));
        }