A [n] [n], где A [i] [j] содержит время, необходимое для того, чтобы добраться из города i в город j (без посещения других городов) (A[i][i] = 0 , I = 0,…, n-1): Необходимо построить матрицу B[n][n], где B[i][j] — минимальное время, необходимое для поездки из города i в город j. Количество шагов, выполняемых алгоритмом, должно быть O (n^3)
Floyd–Warshall algorithm
А другого алгоритма нет?
Dijkstra's algorithm
Немного не понял задачу, нужно выбрать минимум из A[i] [j] и A[j] [i] результат записать в В[i] [j]?
Используй Флойда-Уоршела
A матрица хранит прямую дорогу из города i в город j. Нужно минимальное время найти, чтобы добраться из города i в город j (можем посещать через другие города)
Все понял, спасибо
Обсуждают сегодня