Условие задачи
Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Алгоритм решения
В задаче следует реализовать алгоритм Флойда. В ячейках входной (начальной) матрицы поставим большое натуральное число (вместо -1) вместо кратчайшего пути (если остается это число, значит, пути просто не существует). Затем в матрице кратчайших расстояний следует найти наибольшее число (отличное от нашего максимального, присвоенного в самом начале) – оно и будет максимальным кратчайшим расстоянием.
У нас уже есть имеющиеся пути. Мы вычисляем пути для всех вершин и оставляем кратчайший, то есть:
Если кратчайший путь из u в v, содержащий только вершины из множества {1..i}{1..i}, проходит через вершину i, то кратчайшим путем из u в v является кратчайший путь из u в i, объединенный с кратчайшим путем из i в v. В противном случае, когда этот путь не содержит вершины i, кратчайший путь из u в v, содержащий только вершины из множества {1..i}{1..i} является кратчайшим путем из u в v, содержащим только вершины из множества {1..i−1}{1..i−1}.
Решение на с++
Полное решение смотри на картинке, прикрепленной ниже!
using namespace std;
int main(){ // основная функция программы
int n,i,j,k;
cin>>n; // считывание количества вершин графа
int a[n][n]; // создание матрицы
for(i=0;i<n;++i) // читаем входной граф и построение матрицы смежности
for(j=0;j<n;++j){
cin>>a[i][j];
if(a[i][j]<0)a[i][j]=INF;} // INF - изначально присваиваем большое число для дальнейшего вычисления кратчайшего расстояние. Изначально кратчайшее расстояние INF
for(k=0;k<n;++k) // реализация алгоритма Флойда
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
k=0;
for(i=0;i<n;++i) // нахождение минимального расстояния для вывода ответа
for(j=0;j<n;++j)
if(a[i][j]<INF&&a[i][j]>k)
k=a[i][j];
cout<<k; // вывод ответа
return 0;}
#информатика #программирование #acmp #егэинформатика #репетиторпоинформатике