Алгоритм поиска самого короткого пути между вершинами в графе PySpark
У меня есть таблица вида:
+--------+---+
| src|dst|
+--------+---+
|16447200| 12|
|16929600| 12|
|22550800| 12|
|22829200| 12|
|23675600| 12|
+--------+---+
На несколько тысяч строк. Необходимо найти самый короткий путь из вершины src до вершины dst в графе с помощью Spark. Я пишу на PySpark. Идея состоит в использовании библиотеки graphx для графового представления данных из датафрейма и применении встроенного алгоритмя BFS (поиска в ширину). Пишу следующий код:
- Поиск узлов в графе
verticesDf = e.select('src').union(e.select('dst')).withColumnRenamed("src", "id")
где e - это исходная таблица
- Создание графа
g = GraphFrame(verticesDf, e)
- Алгоритм BFS:
path = g.bfs("id = 15", "id = 37")
И на этом моменте все встает, алгоритм то ли зацикливается, то ли очень долго ищет путь, но результата нет. Помогите, пожалуйста, найти проблему.