Кратчайший путь одной пары в матрице
Пусть матрица MxN, где начало находится в позиции (0,0) и заканчивается в (M-1,N-1) . Каждая клетка имеет положительное целое число, которое представляет собой стоимость перемещения по этой клетке. Какой алгоритм я должен использовать для кратчайшего пути от начала до конца? Мы можем воссоздать задачу с помощью графиков. Где квадраты — это вершины, а затраты — взвешенные ребра.
Пример
Ответы 1
Используйте Дейкстра . Как только вы услышите «кратчайший путь», посмотрите на Дейкстру. В частности, если вы ищете «матрицу смежности Дейкстры» в переполнении стека, вы получите более десятка вопросов, обсуждающих различные аспекты применения Дейкстры к графу, представленному в виде матрицы. Вы можете построить матрицу смежности из вашей входной матрицы, перебирая входные данные следующим образом:
create a (rows * cols) * (rows * cols) adjacency matrix
for each square at position row,col in the input matrix
let v = row*cols + col
for all neighboring positions u (at row,col+1; row+1,col; and so on)
set the cost of going from v to u to input[row][col]
Можно даже не строить матрицу смежности, а просто вычислять соседей и расстояние до соседей на лету. Это может сэкономить довольно много памяти за счет дополнительного времени выполнения.
Вы также можете сэкономить немного места, представив граф в виде списка смежности, но их немного сложнее реализовать, и вы, похоже, только начинаете.