2点間の最小距離を求める

Question

N行で接続されているMポイントがあります。次のNの入力行には、異なる一対の点間の距離が含まれています。私は各点の対の間の最小距離の和を求めたい。

サンプル入力：

5 6 
1 2 23 
1 3 5 
2 3 3 
2 4 12 
3 4 5 
4 5 2 

サンプル出力：

31 

説明：

D（1,2）= 5 + 3 = 8

D（1,3）= 5

D（2,3）= 3

D（2,4）= 3 + 5 = 8

D（3,4）= 5

D（4,5）= 2

和= 8 + 5 + 3 + 8 + 5 + 2 = 31

編集1：

Iは、次のコードを使用してadjanceyマトリックスにwightedグラフに変換した：

Scanner in = new Scanner(System.in); 
    int n = in.nextInt(); 
    int m = in.nextInt(); 
    int[][] vertices = new int[m][m]; 

    for(int i=0; i<m; i++){ 
     for(int j=0; j<m; j++){ 
      vertices[i][j]=0; 
     } 
    } 
    for(int i=0; i < m; i++){ 
      int a = in.nextInt(); 
      int b = in.nextInt(); 
      int c = in.nextInt(); 
      vertices[a][b] = c; 
      vertices[b][a] = c; 
    } 

今どのようにiが与えられた任意の2点間の最短距離は、それらを結ぶ線が存在する見つけることができますか？

Answer 1

Floyd-Warshallを使用して、すべてのペアの最短パスのマトリックスを構築します。行列のすべての値を加算し、2で除算します。これは、各距離を2回カウントするためです。

wikiページの擬似コードは、それをjavaに変換するのに十分です。