Мне нужна рекомендация для эффективной структуры данных, которая удовлетворяет моей задаче расчета затрат на пути внутри ориентированного графа в соответствии с ограничением, что многие пути иногда имеют один и тот же подпуть, для которого я не хочу выполнять вычисления дважды.
Каждое число в этих списках относится к узлу внутри ориентированного графа.Каждая строка описывает один путь:
[121, 85, 135, 99, 141, 134, 4, 33, 65, 131, 18, 127],
[121, 85, 135, 99, 141, 134, 65, 33, 4, 127],
[121, 85, 135, 99, 141, 134, 65, 33, 4, 131, 18, 127],
[121, 85, 135, 99, 141, 134, 65, 33, 4, 107, 127],
[121, 85, 135, 99, 141, 134, 65, 23, 18, 127],
[121, 85, 135, 99, 141, 134, 65, 23, 18, 131, 4, 127],
[121, 85, 135, 99, 141, 134, 65, 23, 18, 131, 4, 107, 127],
[121, 85, 135, 99, 141, 134, 65, 107, 4, 127],
[121, 85, 135, 99, 141, 134, 65, 107, 4, 131, 18, 127],
[121, 85, 135, 99, 141, 134, 65, 107, 127],
[121, 85, 135, 99, 141, 134, 65, 131, 18, 127],
[121, 85, 135, 99, 141, 134, 65, 131, 4, 127],
[121, 85, 135, 99, 141, 134, 65, 131, 4, 107, 127],
[121, 85, 135, 99, 141, 4, 127],
...
Как видно из этого примера, многие пути совместно используют один и тот же набор узлов на этом пути.(И многие другие пути [здесь не показаны] не имеют общего подпути.)
Я хочу вычислить «оптимальность» каждого пути, то есть сумму ИЛИ произведений весов по пути.Эти веса можно рассматривать как постоянные для моего графа при обходе каждого пути.
Для ясности: я хочу избежать вычисления веса пути от узла 121 до узла 141 для всех показанных путей в этом примере, так какэти умножения / сложения весов между двумя узлами одинаковы (до узла 141) в каждом из показанных путей ...
Я удовлетворен рекомендацией и объяснением структуры данных, почему упомянутая структура данных лучше всего подходитдля моих нужд.Если у вас также есть рекомендации по библиотеке, я бы предпочел одну на C / C ++ или Python.