0

あなたのためのグラフアルゴリズムの質問.

道路網を表すために使用されるグラフがあります。そのため、そこにはサイクルがあります（ラウンドアバウトは些細なものです）。また、双方向のエッジもあれば、単方向 (一方通行) のエッジもあります。エッジは、その長さによって重み付けされます。

2 つのノードがあり、それらの間の最短パスが既に計算されているとします。私がやりたいことは、距離 X よりも短い 2 つのノードを接続する他のすべてのパスを見つけることです。これらのパスを「代替」と呼びます。

アスキー アートの例を以下に示します。ここでは、エッジに文字、ノードに数字のラベルを付けています。

         F
      5----6  
   E /      \ G  
    3--------4
   /    D     \
B /            \ C
 1--------------2
        A

1->2 のエッジ A をカバーするパスがあり、代替を見つけたいとします。そのパスの代替の 1 つは、その長さが X 未満であれば、BDC です。BEFGC は別のパスです。

もう 1 つのパスの例は、ノード 1->4 を接続する BD です。その代替は AC です。

その他の要件:

  1. 代替パスには、メイン パスのどの部分も含めないでください。したがって、メイン パスが A の場合、A を含む代替パスは有効な代替パスではありません。1->4 を接続する上記の BD の例では、メイン パスにある B が含まれているため、BEFG は有効な代替手段ではありません。
  2. 代替には内部サイクルがあってはなりません。たとえば、この代替パスは 1->2 の接続には許可されません: BDGFEDC は、エッジ D を 2 回通過するためです。

ありがとう！

4

1 に答える 1