Großes Problem mit Dijkstra-Algorithmus in einer verknüpften Liste Graph Umsetzung

Question

Ich habe meine Grafik mit verknüpften Listen implementiert, sowohl für Ecken und Kanten und das ein Problem für den Dijkstra-Algorithmus wird immer. Als ich auf einer früheren Frage gesagt, ich bin Umwandlung dieser Code dass Anwendungen eine Adjazenzmatrix zur Arbeit mit meiner graph Umsetzung.

Das Problem ist, dass, wenn ich den Minimalwert finde ich einen Array-Index. Dieser Index hätte den Vertex-Index übereinstimmen, wenn die Graph Scheitel statt in einem Array gespeichert wurden. Und der Zugang zum Scheitel würde konstant sein.

Ich habe keine Zeit, um meine Graph Implementierung zu ändern, aber ich habe eine Hash-Tabelle habe, durch eine eindeutige Nummer indiziert (aber eine, die nicht bei 0 beginnt, es ist wie 100.090.000), das ist das Problem, das ich habe, . Jedes Mal, wenn ich brauche, verwende ich den Modulo-Operator eine Zahl zwischen 0 und der Gesamtzahl der Scheitelpunkte zu erhalten.

Das funktioniert gut, wenn ich brauche einen Array-Index aus der Zahl, aber wenn ich brauche die Nummer aus dem Array-Index (für den Zugriff des berechneten minimalen Abstand Scheitel in konstanter Zeit), nicht so sehr.

Ich habe versucht, zu suchen, wie die Modulo-Operation invers, wie, 100090000 mod 18000 = 10000 und 10000 INVMOD 18000 = 100090000 konnte aber nicht einen Weg finden, es zu tun.

Meine nächste Alternative ist eine Art Referenzanordnung, wobei in dem obigen Beispiel, arr zu bauen [10000] = 100090000., das das Problem beheben würde, würde aber einer Schleife erfordert das ganze Diagramm noch einmal.

Muss ich besser / einfachere Lösung mit meiner aktuellen Graphen Implementierung?

Answer 1

In Ihrem Array, anstatt nur die Zählung zu speichern (oder was auch immer Sie speichern dort), speichern Sie eine Struktur, die die Zählung sowie die Vertex-Indexnummer enthält.