Метод Джикстра с использованием пакета cppRouting в R

Question

Я хотел бы знать, как использовать метод dijikstra с использованием пакета cppRouting. Моя база данных содержит данные о расстоянии между различными местоположениями, и я хотел бы использовать этот метод для решения моей проблемы, которая заключается в вычислении кратчайших путей между этими местоположениями. Я исследовал и увидел об этом пакете, который работает с этим методом.

Пакет: https://cran.r-project.org/web/packages/cppRouting/cppRouting.pdf

> df <- read_excel('C:/Users/Local.xlsx')
> df
# A tibble: 6 x 6
         `Local 1`      `Loca 2`    `Local 3`     `Local 4`      `Local 5` `Local 6`
          <dbl>         <dbl>         <dbl>         <dbl>         <dbl>         <dbl>
1            0           350.         1279.         1544.         2393.         2837.
2          350.            0          1365.         1807.         2605.         3159.
3         1279.         1365.            0           946.         1386.         2433.
4         1544.         1807.          946.            0           918.         1502.
5         2393.         2605.         1386.          918.            0          1483.
6         2837.         3159.         2433.         1502.         1483.            0 

Answer 1

Входными данными является график. Граф - это множество вершин (или узлов), соединенных ребрами. График обычно используется для обозначения сети, такой как дороги, где ребра - это отрезок дороги, а узлы - это пересечения. График взвешивается, если у каждого ребра есть вес, описывающий расстояние или время в пути.

Посмотрите на этот тривиальный пример ориентированного графа, давайте предположим, что все ребра имеют одинаковую длину:

В пакете R и cppRouting график должен представлять собой фрейм данных, описывающий каждое ребро:

library(cppRouting)
library(igraph)

graph<-data.frame(from=c(0,1,2,3,4,2),
                  to=c(1,2,3,0,2,4),
                  weight=c(1,1,1,1,1,1))

#visualize 
test<-graph_from_data_frame(graph,directed = TRUE)
plot(test,edge.arrow.size=0.2)

Теперь, если вы хотите узнать кратчайший путь между узлами 0 и 3:

cpp_graph<-makegraph(graph,directed=TRUE)
get_path_pair(cpp_graph,from="0",to="3")

, если вы хотите узнать кратчайшее расстояние:

get_distance_pair(cpp_graph,from="0",to="3")

Надеюсь, что поможет.

Answer 2

Я автор пакета cppRouting. Первичные данные для расчета расстояний или путей - это график, и вы его не предоставляете, он у вас есть?

Вы читаете некоторую матрицу расстояний, я думаю, но каковы ваши входные данные? дорожная сеть?

Прочтите это , чтобы узнать, как использовать пакет cppRouting.