Мой граф реализован со связанными списками, как для вершин, так и для ребер, и это становится проблемой для алгоритма Дейкстры. Как я уже говорил в предыдущем вопросе, я конвертирую этот код , который использует матрицу смежности для работы с моей реализацией графа.
Проблема в том, что когда я нахожу минимальное значение, я получаю индекс массива. Этот индекс соответствовал бы индексу вершин, если бы вершины графа хранились в массиве. И доступ к вершине будет постоянным.
У меня нет времени, чтобы изменить реализацию графа, но у меня есть хеш-таблица, индексируемая уникальным номером (но та, которая не начинается с 0, это как 100090000), и это проблема , Всякий раз, когда мне нужно, я использую оператор по модулю, чтобы получить число от 0 до общего количества вершин.
Это прекрасно работает, когда мне нужен индекс массива из числа, но когда мне нужно число из индекса массива (для доступа к вычисленной минимальной вершине расстояния в постоянное время), не так много.
Я пытался найти способ инвертировать операцию по модулю, например, 100090000 mod 18000 = 10000 и 10000 invmod 18000 = 100090000, но не смог найти способ сделать это.
Моя следующая альтернатива - создать некоторый эталонный массив, где в приведенном выше примере arr [10000] = 100090000. Это решило бы проблему, но потребовало бы зациклить весь график еще раз.
Есть ли у меня лучшее / простое решение с моей текущей реализацией графа?