0

エッジに値があり、ノードに値がない有向巡回グラフがあります。

グラフには開始ノードと終了ノードがあり、グラフを介してパスのセットを保持したいのですが、パス上のノードは気にせず、エッジ値のみを気にします。以下の例。

そのプロパティを保持する小さなグラフを生成するアルゴリズムはありますか?

グラフには数万のノードが含まれる場合がありますが、数百万にはなりません。ノードあたりのエッジの数は、ノードの数に対して少ないです。

保守的なヒューリスティックは大歓迎です。

例として、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] の 2 つのパスがあるため、1 つが冗長であり、上記を

  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

より単純なグラフでは、2 番目の遷移 1 を削除して、自己エッジのみを残します。

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

2 に答える 2

0

最初と最後ではないすべてのノードを繰り返し処理し、それらの削除に進みます。ノードを削除すると、このノードを介して接続されたすべてのノード間に別のエッジが追加されます (有向グラフであるため、方向に注意してください)。覚えておくべきことは、このプロセスのために既に存在するエッジを追加しようとする場合は、重みが小さいエッジを維持することです (これが重要です)。

于 2012-01-06T18:20:04.310 に答える
0

含意チャートは私が必要としていたことをしました。ノード数に関しては O(n**2) 個のスペースがありますが、私の状況では管理可能です。

于 2012-01-20T17:40:08.900 に答える