graph-algorithm - 用于减少图同时保留从开始节点到结束节点的路径的边值的算法

Question

我有一个有向循环图，边缘处有值，但节点处没有值。

该图有一个开始节点和一个结束节点，我想保留通过图的路径集，但我不关心路径上的节点，只关心边缘值。下面的例子。

是否有任何算法可以生成保留该属性的较小图形？

该图可能有数十个数千个节点，但不是数百万个。每个节点的边数比节点数少。

保守的启发式方法是受欢迎的。

举个例子，哪里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

我将遍历所有不是开始和结束的节点并继续删除它们。删除节点时，您在通过该节点连接的所有节点之间添加另一条边（观察方向，因为它是有向图）。要记住的是，如果您尝试添加由于此过程而已经存在的边缘 - 确保保留具有较小权重的边缘（这是关键）。

Answer 2

暗示图表做了我需要的。它们在节点数量上是 O(n**2) 空间方面的，但在我的情况下这是可以管理的。