Мне нужно найти кратчайший путь сети с взвешенными направленными ссылками. Я делал это уже несколько раз с сетями, которые обычно содержали от 500 до 2000 узлов. Следующий код иллюстрирует, как мне удалось получить матрицу расстояний и промежуточные узлы, если это необходимо:
library(e1071)
# Empty matrix:
mx <- matrix(NA, 8, 8)
# Fill a few direct links:
mx[1,5] = 4
mx[3,4] = 5
mx[7,1] = 1
mx[3,7] = 3
mx[4,3] = 2
mx[6,5] = 7
mx[2,8] = 3
mx[5,2] = 9
mx[7,6] = 5
mx.filled = allShortestPaths(mx)
mx.filled$length # distance matrix
extractPath(mx.filled,1,2) # intermediate nodes for path between 1 and 2
Это может быть не элегантно, но работает.
Проблема: IСейчас я занимаюсь сетью из 1 000 000 узлов. Это количество узлов означает, что я должен использовать другой подход, чем построение матрицы и ее заполнение.
Цель: я пытаюсь найти метод, чтобы получить расстояние между источником и пунктом назначения от большогосеть.
Пример связывает как фрейм данных:
link = dplyr::tribble(~From, ~To, ~Distance,
1,5,4,
3,4,5,
7,1,1,
3,7,3,
4,3,2,
6,5,7,
2,8,3,
5,2,9,
7,6,5)
Как бы получить кратчайший путь между, например. от источника 6 до пункта назначения 2, если в сети было несколько миллионов ссылок?
Заранее спасибо