Разбор

В задаче необходимо построить матрицу кратчайших путей между всеми парами вершин графа. Для этого следует реализовать алгоритм Флойда — Уоршела.

Пример

Граф, приведенный в условии, имеет вид:

Реализация алгоритма

Матрицу смежности графа храним в массиве $g$ .

#define MAX 101
int g[MAX][MAX];

Функция floyd реализует алгоритм Флойда — Уоршела.

void floyd(void)
{
  int i, j, k;
  for(k = 0; k < n; k++)
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if (g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j];
}

Основная часть программы. Читаем входной граф.

scanf("%d",&n);
for(i = 0; i <  n; i++)
for(j = 0; j <  n; j++)
  scanf("%d",&g[i][j]);

Запускаем алгоритм Флойда — Уоршела.

floyd();

Выводим матрицу кратчайших расстояний между всеми парами вершин.

for(i = 0; i <  n; i++)
{
  for(j = 0; j <  n; j++)
    printf("%d ",g[i][j]);
  printf("\n");
}

Java реализация

import java.util.*;

public class Main 
{
  static int g[][];
  static int n;
  
  static void floyd()
  {
    for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (g[i][k] + g[k][j] < g[i][j]) 
        g[i][j] = g[i][k] + g[k][j];
  }
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);	  
    n = con.nextInt();
    g = new int[n][n];

    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      g[i][j] = con.nextInt();

    floyd();

    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
    	  System.out.print(g[i][j] + " ");
      System.out.println();
    }
    con.close();
  }
}

Python реализация

Функция floyd реализует алгоритм Флойда — Уоршела.

def floyd():
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if g[i][k] + g[k][j] < g[i][j]:
           g[i][j] = g[i][k] + g[k][j]

Основная часть программы. Читаем входной граф.

n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
  g[i] = list(map(int, input().split()))

Запускаем алгоритм Флойда — Уоршела.

floyd()

Выводим матрицу кратчайших расстояний между всеми парами вершин.

for i in range(n):
  print(*g[i])