Рассчитать количество вершин на кратчайшем пути. - PullRequest
Новая
       19

Рассчитать количество вершин на кратчайшем пути.

0 голосов
/ 09 мая 2018

Имея взвешенную направленную сеть, такую ​​как эта: 

library(igraph)

g <- erdos.renyi.game(25, 1/10, directed = TRUE)
E(g)$weight <- runif(length(E(g)), 1, 5)

При выполнении функции кратчайшего пути sp <- shortest.paths(g) я, очевидно, получаю матрицу с суммой взвешенных ребер между ними. Однако я хотел бы посчитать, сколько вершин на этом пути.

Идея заключается в поиске кратчайших путей для сети поездов, с ребрами в качестве железнодорожных станций, в том смысле, что я хотел бы видеть количество передач (между вершинами или узлами) для каждого кратчайшего пути.

РЕДАКТИРОВАТЬ: Например, если кратчайший путь от А до С, я хочу знать, сколько вершин между ними. Например, если полный путь A - E - B - C, то E и B являются промежуточными вершинами, поэтому у меня будет значение 2. Полный путь вершин также в порядке, так что в этом случае это даст мне 4 вершины для полного кратчайшего пути.

1 Ответ

0 голосов
/ 09 мая 2018

Найден альтернативный вариант решения проблемы. 

sp <- shortest_paths(g, V(g), V(g), mode = "all",
                         weights = E(g)$weight, output = "vpath")$vpath

lengths(sp)

Это дает точное количество вершин на этом пути.Таким образом, для промежуточных остановок нужно просто вычесть 2 в значение.

...