Создание матрицы расстояний matrica <- matrix(rep(99999, 400), nrow = 20, ncol = 20) for…
- User
Создание матрицы расстояний
matrica <- matrix(rep(99999, 400), nrow = 20, ncol = 20) for (i in 1:20) { for (j in 1:20) { if (i == j || i %% 5 == 0 || j %% 5 == 0) { matrica[i, j] <- 1 } } }
Функция для алгоритма Флойда-Уоршелла
floyd_warshall <- function(matrica) { n <- nrow(matrica) for (k in 1:n) { for (i in 1:n) { for (j in 1:n) { if (matrica[i, j] > matrica[i, k] + matrica[k, j]) { matrica[i, j] <- matrica[i,k] + matrica[k, j] } } } } return(matrica) }
Вызов функции для матрицы расстояний и вывод кратчайшего расстояния между точками 2 и 19
result <- floyd_warshall(matrica) result[2, 19]
Данный алгоритм возвращает кратчайшее расстояние между двумя точками,а нужна траектория движения
- Assistant
Для получения траектории движения нужно модифицировать алгоритм Флойда-Уоршелла, чтобы он запоминал не только кратчайшие расстояния, но и пути, соединяющие каждую пару вершин.
Функция для алгоритма Флойда-Уоршелла с запоминанием путей
floyd_warshall_path <- function(matrica) { n <- nrow(matrica) path <- matrix(rep(0, n^2), nrow = n, ncol = n) for (i in 1:n) { for (j in 1:n) { if (matrica[i, j] < 99999) { path[i,j] <- j } } } for (k in 1:n) { for (i in 1:n) { for (j in 1:n) { if (matrica[i, j] > matrica[i, k] + matrica[k, j]) { matrica[i, j] <- matrica[i,k] + matrica[k, j] path[i, j] <- path[i,k] } } } } return(list(dist = matrica, path = path)) }
Вызов функции для матрицы расстояний и вывод пути между точками 2 и 19
result <- floyd_warshall_path(matrica) path <- c(2) while (path[length(path)] != 19) { path <- c(path, result$path[path[length(path)], 19]) } print(paste("Путь между точками 2 и 19:", paste(path, collapse="->")))
Результат выполнения функции должен вернуть путь между точками 2 и 19 для данной матрицы расстояний.