Berechnen des kürzesten Pfades vom Set-Knoten zu allen anderen Knoten, wobei einige Knoten vom Pfad aus verboten sind

Question

Ich möchte Folgendes in Python implementieren, aber nicht sicher, wo ich anfangen soll. Gibt es gute Module für solche Probleme?

Ich versuche, den kürzesten Weg von einem bestimmten Atom (node) an alle anderen Atom (Knoten) in einer gegebenen Sammlung von XYZ-Koordinaten für eine 3D-chemische Struktur (der Graph) zu definieren. Die Bindungen zwischen den Atomen (Knoten) sind die Kanten, für die eine Wanderung von Knoten zu Knoten erlaubt ist.

Ich versuche, bestimmte Atome (Knoten) aus dem Molekül (Graph) basierend auf der Konnektivität nach außen von einem ausgewählten zentralen Knoten herauszufiltern.

** Für die betrachteten Pfade möchte ich verhindern, dass bestimmte Atome (Knoten) gekreuzt werden. Wenn der kürzeste Weg von A nach B durch einen verbotenen Knoten verläuft, ist diese Antwort nicht erlaubt. Der kürzeste Pfad von A nach B darf den verbotenen Knoten nicht enthalten. **

Wenn der kürzeste Pfad vom ausgewählten Zentralatom (A) zu einem anderen Knoten (B) den verbotenen Knoten enthält, UND ist kein anderer Pfad verfügbar von A nach B durch die verfügbaren Kanten (Bindungen), dann sollte Knoten B aus dem endgültigen Satz von zu speichernden xyz-Koordinaten (Knoten) gelöscht werden.

Dies sollte für A zu C, A zu D, A zu E usw. für alle anderen Atome (Knoten) in der Struktur (Graph) wiederholt werden.

Vielen Dank im Voraus für jede Hilfe, die Sie anbieten können.

Answer 1

Stellen Sie sicher, dass alle Kanten, die zu den verbotenen Knoten führen würden, unendlich viele Kosten haben und der von Ihnen verwendete Graph-Traversing-Algorithmus automatisch damit umgehen wird.

Alternativ entfernen Sie einfach die verbotenen Knoten vom Graph Traversal-Algorithmus.

Answer 2

Um den ersten Teil Ihrer Frage zu beantworten, empfehle ich networkx. Es ist eine universelle grafische Bibliothek, die ziemlich leicht zu bekommen ist (ich habe es in meiner Doktorarbeit verwendet).