Кратчайший маршрут между несколькими точками

Мне нужно найти кратчайший маршрут между несколькими точками. Допустим, у меня есть следующие четыре пункта:

var startPoint = new Point(1, 1);
var pointsToGoPast = new List<Point> { new Point(3,1); new Point(2,4); };
var endPoint = new Point(10, 10);

Итак, я хочу выяснить, какие точки нужно пройти в первую очередь, чтобы получить кратчайший путь от начальной точки до конечной точки.

Может кто-нибудь мне помочь?

Обновление: он должен пройти мимо каждой из точек в списке pointsToGoPast. Стоимость указана даже для каждого маршрута.

 TheEvilPenguin04 июн. 2012 г., 01:57
Хотите посетить каждую точку или просто найти кратчайший путь? Кратчайший путь легче, посетить каждую точку намного сложнее. Поиск проблемы коммивояжера для обзора сложности.
 Alex Filatov08 сент. 2016 г., 22:12
Возможный дубликатCalculating the shortest route between two points
 Imre L04 июн. 2012 г., 00:42
Вы можете двигаться из любой точки в любую точку напрямую? Сколько стоит 2 балла? Я бы пошел сen.wikipedia.org/wiki/Dijkstra's_algorithm
 Hans Passant04 июн. 2012 г., 00:44
Дейкстра решил эту проблему еще в шестидесятых. Он ушел, вам придется применить его алгоритм самостоятельно:en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Ответы на вопрос(4)

неясно, какова стоимость перехода из одной точки в другую. Это просто расстояние между этими точками? В любом случае, несмотря на это, такую проблему можно решить с помощью обычного линейного программирования. Я только что закончил создание библиотеки C #, чтобы упростить проблемы кратчайшего пути. ЗагружаемыеВот.

Над этой библиотекой еще много работы, но она должна дать вам то, что вы хотите, очень простым способом.

С Уважением,

Брюс.

Решение Вопроса

Пример проекта с кодом здесь

Единственное, что нужно изменить, - это вес в проекте, поскольку вес основан на расстоянии между двумя точками. (Так что вам нужно изменитьLocation хранитьPoint иConnection рассчитать вес (расстояние) в конструкторе.

В Википедии есть очень хорошая статья об алгоритме

Алгоритм Дейкстры

{        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

select geography :: Point(@PointALatitude, @PointALongitude, 4326).STDistance(geography::Point(@PointBLatitude, @PointBLongitude, 4326))

Результат возвращается в метрах, поэтому просто разделите на 1000 для Км или 1609.344 для Миль

Ваш ответ на вопрос