Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 124 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                  .
пути из j в i.

    // определение функции построения всех кратчайших
    // путей в графе с помощью алгоритма Флойда
    void Floyd(Graph2 g, int**& H, int**& T)
    {
          int i,k,j;
          // выделение памяти под матрицу длин кратчайших путей T
          // и матрицу путей H
          T=new int*[g.n];
          H=new int*[g.n];
          for(i=0;i < g.n;i++)
          {
               T[i]=new int[g.n];
               H[i]=new int[g.n];
          }
          // начальная инициализация матриц T и H согласно
          // матрице смежности графа
          for(i=0;i < g.n;i++)
               for(j=0;j< g.n;j++)
               {
                    T[i][j]=g.a[i][j];
                    if(g.a[i][j]==MAX_INT) H[i][j]=0;
                    else H[i][j]=j+1;
               }
          for(i=0;i< g.n;i++)
          {
               for(j=0;j< g.n;j++)
                    for(k=0;k< g.n;k++)
                         // если можно проехать из j-ой вершины в
                         // k-ую через i-ую более коротким путем,
                         // меняем длину T[j][k] и путь
                         if(i!=j && i!=k && T [j][i]!=MAX_INT &&
                               T[i][k]!= MAX_INT &&
                               T[j][k]>T[j][i]+T[i][k])
                         {
                              H[j][k]=H[j][i];
                              T[j][k]=T[j][i]+T[i][k];
                         }
          }
    }

    Задача 6. Дан взвешенный граф в виде матрицы смежности. Найти диа-
метр графа, т.е. максимальное расстояние между всевозможными парами его
вершин.
                                           124