Нахождение минимального расстояния между двумя точками

Question

У меня есть M Точки, которые связаны N линий. Следующие N строки ввода содержат расстояние между различными парами точек. Я хочу найти сумму минимального расстояния между каждой парой точек.

Пример ввода:

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

Пример вывода:

31 

Объяснение:

д (1,2) = 5 + 3 = 8

д (1,3) = 5

д (2,3) = 3

д (2,4) = 3 + 5 = 8

д (3,4) = 5

д (4,5) = 2

сумма = 8 + 5 + 3 + 8 + 5 + 2 = 31

Edit 1:

Я преобразовал wighted граф в adjancey матрицу, используя следующий код:

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; 
    } 

Теперь, как я могу найти кратчайшее расстояние между любыми двумя точками, заданными там существует линия, соединяющая их?

Answer 1

Использовать Floyd-Warshall для построения матрицы всех пар кратчайших путей. Теперь добавьте все значения в матрицу и разделите на 2, потому что вы будете считать каждое расстояние дважды.

Псевдокод на странице wiki более чем достаточно, чтобы преобразовать его в java.