Мне нужно реализовать рекурсивный алгоритм, который дает мне ВСЕ кратчайшие пути в двумерном массиве.Я хочу знать, возможно ли это сделать с помощью алгоритма Дейкстры или его адаптации или вы порекомендуете другой алгоритм для их поиска.Таким образом, у меня есть r строк и c столбцов, и есть r * c точек, связанных с ортогональными и диагональными соседними точками.Мне нужен алгоритм, который подсчитывает количество кратчайших путей от нижней правой точки (mat [r] [c]) до верхней левой (mat [0] [0]).
Этот алгоритм уже делаетработа, я имею в виду, вопрос в том, сколько таких путей существует, а не в длине этих путей.
static int numShortestLinks(int r, int c) {
if ((r==0) || (c==0)) {
return 0;
}
if ((r==1) || (c==1)) {
return 1;
}
return numShortestLinks(r-1,c-1) + numShortestLinks(r-1,c);
}
int mat[][] = new int [4][2];
System.out.println(numShortestLinks(mat.length,mat[0].length));
Этот код возвращает 4, и, насколько я могу судить, существует 4 кратчайших пути.