Kürzeste route zwischen mehreren Punkten

Ich muss die kürzeste Strecke zwischen mehreren Punkten. Lassen Sie uns sagen, dass ich diese vier Punkte:

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);

So, ich möchte, um herauszufinden, welche Punkte gehen vorbei an den ersten, um die kürzeste route vom Startpunkt zum Endpunkt.

Kann mir jemand helfen?

Update: Es hat zu gehen, hinter jeder der Punkte in der pointsToGoPast Liste. Die Kosten sind auch für jede route.

Sie kann sich von jedem Punkt zu jedem Punkt direkt? Was die Kosten zwischen 2 Punkten? Ich würde mit dem en.wikipedia.org/wiki/Dijkstra's_algorithm
Dijkstra löst dieses problem wieder in den sechziger Jahren. Er ist nun Weg, haben Sie, um den Algorithmus selbst: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Wollen Sie jedem zeigen, oder einfach nur den kürzesten Weg zu finden? Kürzeste Weg ist leichter, zu besuchen, jeder Punkt ist viel schwieriger. Suche für die Travelling-Salesman-problem für einen überblick über die Komplexität.
Möglich, Duplikat der die Berechnung der kürzesten route zwischen zwei Punkten

InformationsquelleAutor Martin | 2012-06-03

2d c#geometry math

6

Können Sie dies tun, indem Sie Dijkstra ' s Algorithmus.

Beispiel-Projekt mit dem code hier

Das einzige, was sich ändern muss ist, das die GEWICHTE in das Projekt, da das Gewicht auf der Grundlage der Entfernung zwischen den beiden Punkten. (So müssen Sie zum ändern der Location zu speichern Point und die Connection zu berechnen, das Gewicht (Distanz) in den Konstruktor.

Wikipedia hat einen sehr schönen Artikel über den Algorithmus

InformationsquelleAutor justderb

Der Dijkstra-Algorithmus

class Dijkstra
{        
        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("");                
            }
        }
 }

InformationsquelleAutor Ahmed Ghoneim

3

Wie bereits darauf hingewiesen worden, es ist nicht klar, was das Kosten wird, der sich von einem Punkt zu einem anderen Punkt. Ist es nur die Distanz zwischen den Punkten?
Trotzdem, unabhängig davon, wie ein problem gelöst werden kann mit herkömmlichen Linearen Programmierung.
Ich habe gerade fertig macht eine C# - Bibliothek zur Vereinfachung der kürzeste-Pfad-Probleme. Herunterladbare hier.

Es ist noch mehr Arbeit zu tun, die auf dieser Bibliothek, aber es sollte Sie geben, was Sie möchten, in einer sehr einfachen Art und Weise.

Grüße,

Bruce.

InformationsquelleAutor Bruce MacDonald
2

Gelöst werden kann, einfach wenn Sie die SQL server
```
select geography :: Point(@PointALatitude, @PointALongitude, 4326).STDistance(geography::Point(@PointBLatitude, @PointBLongitude, 4326))
```
Ergebnis zurückgegeben wird, in Meter so gerade Division durch 1000 für Km oder 1609.344 für Meilen

InformationsquelleAutor Lloydz1

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.