Поиск соседей в 1-х, 2-х, ..., k-хопах в Python с использованием Networkx - PullRequest
Новая
       45

Поиск соседей в 1-х, 2-х, ..., k-хопах в Python с использованием Networkx

2 голосов
/ 19 апреля 2019

Я пытаюсь найти 1-прыжковый, 2-прыжковый и, при необходимости, соседей k-прыжка некоторых определенных узлов (скажем, l узлов) в графе, используя nx.single_source_dijkstra_path_length.

  1. какова временная сложность в зависимости от каждого шага (1-прыжок, 2-прыжок, ...) и
  2. существует ли более быстрый алгоритм?

1 Ответ

0 голосов
/ 20 апреля 2019

Если вы смотрите на невзвешенный график, вы можете использовать поиск в ширину, а сложность по времени для малых k должна быть в среднем O(<k>^k), где <k> - средняя степень рассматриваемого графика.

Если вы хотите рассчитать несколько расстояний на взвешенном графике, вам лучше использовать multi_source_dijkstra_path_length .Я не уверен, какое время выполнения имеет этот алгоритм, но, вероятно, это улучшение по сравнению с несколькими запусками Dijkstra, который имеет O(|V|log(|V|)+|E|) (в зависимости от реализации).

Если вы хотите использовать пороговое значение,Максимальное расстояние в взвешенном графике, оно, вероятно, зависит от распределения веса на ваших ребрах и минимального или среднего веса ребра, который влияет на количество узлов, необходимых для вычисления, чтобы достичь порога.

...