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

Question

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

Граф имеет начальный узел и конечный узел, и я хочу сохранить набор путей через граф, но меня не волнуют узлы на пути, только значения ребер. Пример ниже.

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

График может иметь десятки тысяч узлов, но не миллионы. Количество ребер в узле мало w.r.t. количество узлов.

Консервативная эвристика приветствуется.

Например, где O - это узел, а число - это значение смежного ребра:

  O --------> O -------> O 
    2         3
  ^                      |4
  |1                     v
      1    2    3    4
start -> O -> O -> O -> end

  |5                     ^
  v                      |8

  O --------> O -------> O
    6           7

имеет два пути со значениями ребер [1,2,3,4] от начала до конца, поэтому один из них является избыточным, и я был бы рад уменьшить приведенное выше значение до

  O --------> O -------> O 
    2         3
  ^                      |4
  |1                     v

start                    end

  |5                     ^
  v                      |8

  O --------> O -------> O
    6           7

График может быть циклическим, поэтому в

          1
         /-\
         | /
         v/
start -> O -> O -> end
      1    1    2

более простой график исключил бы второй переход 1, оставив только само-край:

          1
         /-\
         | /
         v/
start -> O -> end
      1    2

Answer 1

Диаграммы последствий сделал то, что мне нужно.Они по O (n ** 2) по количеству узлов, но в моей ситуации это возможно.

Answer 2

Я бы перебрал все узлы, которые не являются началом и концом, и продолжил бы их удаление.При удалении узла вы добавляете еще одно ребро между всеми узлами, которые были соединены через этот узел (следите за направлением, поскольку это ориентированный граф).Следует помнить, что, если вы попытаетесь добавить ребро, которое уже существует из-за этого процесса, убедитесь, что оно осталось с меньшим весом (это ключ).