開始ノードから終了ノードまでの経路に沿ってエッジ値を保存しながらグラフを縮小するアルゴリズム

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 

は、エッジ値を持つ2つの経路を有している[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

Implication Charts私は必要なものをしました。彼らはノード数については空間的にはO（n ** 2）ですが、それは私の状況では扱いやすいものです。

Answer 2

Iは、開始と終了ではないすべてのノードを反復処理し、それらを除去するために進行します。ノードを削除するときは、このノードを介して接続されたすべてのノード間に別のエッジを追加します（有向グラフ以降の監視方向）。忘れてはならないのは、このプロセスのためにすでに存在するエッジを追加しようとする場合、エッジがより小さなウェイト（キー）であることを確認してください。