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