Итак, у меня есть необработанный файл размером 250×200 пикселей, который я прочитал в двумерный массив, например rawFile[250][200]
при этом каждый пиксель (каждый индекс массива) выступает в качестве узла, а каждое значение пикселя представляет высоту (например, топографическая карта). Я хочу найти кратчайший путь, используя алгоритм Дейкстры из rawFile[0][0]
в rawFile[250][200]
при этом стоимость расстояния является абсолютной величиной разницы от node1
в node2
плюс кратчайшее расстояние до текущего посещенного узла. Каждый узел может двигаться в четырех основных направлениях (N, E, S, W), предполагая, что в соответствующем направлении есть соседний узел. Я читал псевдокод и различные реализации, которые все требуют матрицы смежности или списка смежности, который в этом случае будет adjMatrix[50000][50000]
, Однако я изо всех сил пытаюсь выяснить, как я могу заполнить матрицу смежности только из необработанного файла.
Есть ли у вас какие-либо предложения по решению этой проблемы? Спасибо!
Преобразование изображения в матрицу смежности совершенно не нужно; единственное, что вам нужно, это информация о «соседстве», которая уже присутствует неявно.
Соседи любого пикселя i,j
представлены пикселями в (i-1,j), (i+1,j), (i,j-1), (i,j+1)
с учетом границ изображения. Вам не нужна матрица для ее кодирования; всякий раз, когда алгоритм говорит смотреть на соседей, просто предоставьте соседние пиксели.