алгоритм кратчайшего пути без загрузки графа в память - PullRequest
Новая
       25

алгоритм кратчайшего пути без загрузки графа в память

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

https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.all_shortest_paths.html#networkx .algorithms.shortest_paths.generi c .all_shortest_paths

Мне нужно найти все кратчайшие пути с учетом исходного и целевого узлов.

networkx имеет функцию для вычисления всех кратчайших путей. Но для этого необходимо сначала построить весь граф.

Во многих случаях кратчайшие пути могут быть простыми. Например, если вход представляет собой TSV с каждым ребром в строке, а целевой узел и узел-источник уже имеют ребро между ними, нет необходимости сначала строить такой граф в networkx.

Существует ли эффективный алгоритм поиска всех кратчайших путей, чтобы граф строился только тогда, когда это необходимо?

РЕДАКТИРОВАТЬ:

Для начала a и конца d.

Вход: 

a   a
a   b
b   c
c   d
b   1
1   d

Выход: 

a   b   1   d
a   b   c   d
...