Список всех возможных кратчайших путей

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

Моя проблема, к сожалению, довольно сложная. Но я постараюсь облегчить понимание, объясняя даже самые простые вещи. В общем, мне нужно найти комбинации, чтобы добраться до узлов, на которых заканчивается дерево.

На рисунке ниже показан тривиальный пример:

В этом случае B, D, F, H являются конечными узлами, тогда как начальная точка обозначается O. Итак, комбинация путей может быть:

OAB
OCD
OED
OEF
OH
OGH

Однако на самом деле я ищу «самые короткие» или «наиболее подходящие» пути для достижения конечных узлов. Диаграмма (или края) не дает никакой информации о «стоимости» пути. Оценка стоимости будет произведена по результатам найденных комбинаций. Оценка «фактических» затрат на найденные комбинации требует больших вычислительных затрат. Хотя диаграмма не дает много информации, ясно одно: для достижения H, OH в любое время лучше, чем OGH. Таким образом, комбинацию OGH можно исключить из списка возможных комбинаций. По сути, это похоже на метрику расстояния.

Еще одна точка, на самом деле D и F соответствуют эквивалентным точкам (они являются разными узлами, но имеют то же значение для моего приложения). Однако такая информация может быть получена только в том случае, если два узла

- see each other
- see exactly the same nodes

Если внимательно посмотреть на рисунок, можно также понять, что C и E являются эквивалентными узлами. Итак, чтобы сформулировать это более конкретно: комбинации OCD и OED на самом деле одинаковы. После того, как OCD добавлен в список комбинаций, нет необходимости добавлять OED. Это также видно из рисунка, поскольку D и F одинаковы, после добавления OCD в список нет необходимости добавлять OCF.

Подводя итог, решение в этом случае было бы:

OAB
anyone of OCD, OED, OCF, OEF
OH

Чтобы набросать эту биграмму, я следовал руководствам networkx, а затем создал код ниже:

import networkx as nx
import matplotlib.pyplot as plt

graph = [('O', 'A'), ('O', 'C'),  ('O', 'E'),  ('O', 'G'),  ('O', 'H'),  
         ('A', 'B'), ('A', 'O'),
         ('B', 'A'),
         ('C', 'D'), ('C', 'E'), ('C', 'F'), ('C', 'O'),
         ('D', 'E'), ('D', 'C'), ('D', 'F'),  
         ('E', 'C'), ('E', 'D'), ('E', 'F'), ('E', 'O'),
         ('F', 'C'), ('F', 'D'), ('F', 'E'),
         ('G', 'H'), ('G', 'O'), 
         ('H', 'G'), ('H', 'O')]

G=nx.DiGraph()
for edge in graph:
    G.add_edge(edge[0], edge[1])

pos=nx.graphviz_layout(G,prog='dot')
nx.draw(G, pos)
plt.show()

Итак, мой вопрос - перечислить такие последовательности с помощью любого набора инструментов, но желательно networkx. Вероятно, первым делом необходимо упростить (или уменьшить) график перед созданием объекта Graph. После получения упрощенного графика с помощью команды nx.all_simple_path можно перечислить все альтернативные пути. Мне нужна ваша помощь в сокращении такого графика.

Мои графики неглубокие, они обычно примерно того же размера, что и в примере.