余分なエッジなしでAからBまでの最短パス（Javaの場合）

Question

単純な無向グラフを作成し、2つのポイント間のパスを計算し、結果のパスの容量を計算する必要がある割り当てがあります。

私は容量計算を行っています。パスのプリントアウトには、2つのポイント間のパスも見つかることがわかりますが、コードを完全に破損することなく、デッドエンドになるエッジを取り除くことはできません。私は行き止まりから戻ってバウンスを指定しようとしましたが、私はこれまで働いていません。複数エッジの頂点を使用するパスは、現在、そのポイントがパスの中央にあるかどうかに関係なく、その頂点に接続されているすべてのエッジを表示します。基本的には、与えられた点の間のすべての辺、さらに余分な辺をカバーします。

これまでのコードは以下のとおりです。行き先エッジをパスから削除しようとする私の試みはコメントアウトされていますが、まだそこにはコメントアウトされています。

誰でもこの問題を解決できますか？

---

public Queue<Edge> SearchPaths(Vertex x, Vertex eelmine) { 

     if(visited.isEmpty()) 
      lopp = x; // ?? start = x; ?? 

     if(visited.indexOf(x) > -1) 
      return null; 

     if(x.isEquals(lopp)) { 
      Edge serv = x.leiaServ(eelmine); 
      if(serv != null) 
       rajad.add(serv); 
     } 

     Edge serv = x.first; 
     while (serv != null) { 
      if(visited.indexOf(serv.target) == -1) 
       if(serv != null) 
        rajad.add(serv); 
      serv = serv.next; // ?? serv += serv.next 
     } 
     visited.add(x); 

     // otsi uuest tipust järgmine serv 
     if(visited.indexOf(x.first.target) == -1) { 
      Vertex jarg = x.first.target; 

     Edge uusserv = jarg.leiaServ(x); 
     if(uusserv != null) 
      rajad.add(uusserv); 
     SearchPaths(jarg, x); 


      /* "dead-end edges" .. not correct, breaks code 

      // nt. x=C, jarg=D, D != lopp ... jarg.jarg == C (C-D-C) 
      if(jarg!=lopp && visited.indexOf(jarg.first.target) != -1) 
        jarg.equals(x); 

      // x=C, jarg=E, E == lopp ... x == jarg 
      // x=C, jarg=A, A != lopp ... jarg.jarg == B (C-A-B) 
      if(jarg!=lopp && visited.indexOf(jarg.first.target) == -1) { 
       jarg.leiaServ(x); 
       rajad.add(serv); 
       x.equals(jarg); // liiguta x edasi 
       SearchPaths(jarg, x); 
      }*/ 
     } 
     return rajad; 
    } 
} // Vertex ehk Tipp 

Answer 1

あなたはプライオリティキューを使用して、それを実装した場合、Djikstra's algorithmを参照してください、あなただけの行き止まりに達しており、それが再び訪問されることはありませんパスに「無限」重量を配置する必要があります。

「最小」優先度キューは、最小重み付きの要素をポップするデータ構造です。したがって、トラバースしているときは、各トラバーサルのキューを構築します（ノードの隣に歩いて）。

• 何エッジ（リーフノードである）（ラウンドアバウト巡回トラバーサルを避けるために）あなたは既に通過してきたノードへ
• エッジ

を：だから、あなたは持っていないのいずれかのノードに到達した場合

次に、パスに最大の重みを付けるだけです。 Javaの場合、intまたはLong.MAX_VALUEの場合はをlongとします。