加重グラフのノードから他のすべてのノードまでの距離を求める

Question

グラフ内の特定のノードから他のすべてのノードまでの距離を見つけて保存するにはどうすればよいですか？グラフは非周期的であることに注意してください。

これは私が始めたコードです。頂点、訪問先配列、最初に0に設定された2つのノード間の距離行列、
、および現在のノードがどのくらい現在のノードが私がターゲットとして与えたルートノードからの距離であるかを想定していたdistを渡します。
私はDFSを使用し、次のノードに行くたびに前の
の距離にそれらの間の距離を加え、それが存在すれば次の接続への引数として渡します。
私はそれを完了するために手伝ってください。

void DFSUtil(int v,boolean visited[],ArrayList<ArrayList<Integer>> distanceMatrix,int dist,int targ) 
    { 
     // Mark the current node as visited and print it 
     visited[v]=true; 
     System.out.print(v+" "); 


     // Recur for all the vertices adjacent to this vertex 
     Iterator<Integer> i = adj[v].listIterator(); 

     while (i.hasNext()) 
     { 
      int n = i.next(); 

      if (!visited[n]){ 
       /* dist += distanceMatrix.get(v).get(n); 
       System.out.println("cur:"+v+" next:"+n+"\ndistMatrix:"+distanceMatrix.get(v).get(n)+"dist:"+dist); 

       distanceMatrix.get(targ).set(n,dist); 
       distanceMatrix.get(n).set(targ,dist); 
       System.out.println(distanceMatrix); 
       System.out.println();*/ 
       DFSUtil(n, visited,distanceMatrix,dist,targ); 
      } 
     } 
     //remove dist from root to this node 
    } 

Answer 1

私はあなたが有向非循環グラフを意味すると仮定しています。 O（E + VlogV）で動作するDijkstraを使うことができます。

Answer 2

すべてのペアの最短経路問題をお探しの場合は、Floyd-Warshall Algorithmを使用できます。