Punkt-zu-Punkt-Pfad in einem Graphen

Ich möchte einen Algorithmus in der Lage sein, einen optimalen Pfad zwischen zwei Vertices auf einem Graphen zu finden (mit positiven int-Gewichten). Die Sache ist mein Graph ist relativ groß (bis zu 100 Vertices). Ich habe den Dijkstra-Algorithmus betrachtet, aber als ich das Netz durchsucht habe, verwenden die meisten Implementierungen die Adjazenzmatrix, die in meinem Fall 100x100 sein wird.Punkt-zu-Punkt-Pfad in einem Graphen

Wenn Sie mir eine bestimmte Quelle empfehlen könnten, um zu lesen und zu lernen, oder besser, mir eine C++ - Implementierung zu geben, wird es großartig.

PS: Der Algorithmus muss die erforderliche Route und nicht nur die kürzeste Entfernung zwischen zwei Punkten ausgeben.

Vielen Dank für Ihre Zeit.

Quelle

2016-07-06 George P

Wie wäre es [A * -Algorithmus] (https://en.wikipedia.org/wiki/A*_search_algorithm) - es dauert das Beste aus dijkstra und Greedy-Algorithmus und wird in vielen Videospielen verwendet. Hier kommt C++ - Implementierung: http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/ – bashis

Ok, ich werde es vor, ich fand eine Implementierung zusammen mit einem Tutorial.Thank Sie –

Haben Sie sich A* angesehen?

Hier ist ein guter Artikel starten Lesung: http://www.redblobgames.com/pathfinding/a-star/introduction.html

Quelle

2016-07-06 15:18:44

Ich habe den A * -Algorithmus mit dem von Wikipedia bereitgestellten Pseudocode implementiert. Es scheint gut zu funktionieren, aber ich kann einen kleinen Teil im Pseudocode nicht verstehen, um genauer zu sein. Ich kann nicht verstehen, was die Rekonstruktionsfunktion tut. Was ist der total_path, ein Array? Wenn Sie diese spezielle Funktion etwas erklären könnten, wäre das großartig. [Wikipedia] (https://en.wikipedia.org/wiki/A*_search_algorithm) –

Punkt-zu-Punkt-Pfad in einem Graphen

Antwort

Verwandte Themen