Определение кратчайших путей по матричному методу.

[bagfinder]

Помогите разобраться в коде.

Метод определения кратчайших путей в интегрированных вычислительных сетях при использовании дисперсионной матрицы.

Программа получает на вход матрицу расстояний L1 и выводит матрицы L2, L3, L4, матрицу D, матрицу G и матрицу DELTA.
В данном случае у нас матрица 5х5, т.к. всего 5 узлов.


Как вычисляются матрицы L-1..DELTA мне примерно ясно.
А как формируется последняя матрица (дисперсионная матрица)?
На примере четвертого элемента во второй строке (D).

Вывод программы прикреплен.

Матрица расстояний L1:

int L1[5][5]={
0, 20, 999, 999, 35,
20, 0, 20, 30, 999,
40, 10, 0, 15, 999,
999, 30, 15, 0, 999,
999, 999, 15, 40, 0,
};

#include <iostream>
#include <conio.h>
#include <math.h>
#pragma hdrstop
using std::cout;
using std::cin;
using std::endl;

//---------------------------------------------------------------------------
void view(int L[5][5]);
void viewstr(char S[5][5]);
void kw(int L_1[5][5], int L_2[5][5]);
void press();
//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{ char s[]="ABCDE";
int L1[5][5]={ 			
					0, 20, 999, 999, 35,
             				20, 0, 20, 30, 999,
					40, 10, 0, 15, 999,
					999, 30, 15, 0, 999,
					999, 999, 15, 40, 0,	
  };

cout<<endl<<"Matrica L1"<<endl<<endl;
view(L1); press();

int L2[5][5];
for(int i=0;i<=4;i++)for(int j=0;j<=4;j++)L2[i][j]=999;
kw(L1,L2);
cout<<endl<<"Matrica L2"<<endl<<endl;
view(L2);press();

int L3[5][5];
for(int i=0;i<=4;i++)for(int j=0;j<=4;j++)L3[i][j]=999;
cout<<endl<<"Matrica L3"<<endl<<endl;
kw(L2,L3);
view(L3); press();

int L4[5][5];
for(int i=0;i<=4;i++)for(int j=0;j<=4;j++)L4[i][j]=999;
cout<<endl<<"Matrica L4"<<endl<<endl;
kw(L3,L4);
view(L4); press();

cout<<endl<<"Matrica L4=L3 => Matrica D=L3 "<<endl
<<endl<<"Matrica D"<<endl<<endl;
view(L3); press();

int G[5][5];
for(int i=0; i<=4; i++)
 for(int j=0; j<=4; j++)
 if (L1[i][j]==0)G[i][j]=999;else G[i][j]=L1[i][j];
cout<<endl<<"Matrica G"<<endl<<endl;
view(G);press();


int DELTA[5][5];
char dis[5][5];
for(int i=0;i<=4;i++)for(int j=0;j<=4;j++)DELTA[i][j]=999;
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
for(int k=0;k<=4;k++) {
 if (DELTA[i][j]>(G[i][k]+L4[k][j])){DELTA[i][j]=(G[i][k]+L4[k][j]);
                                                     dis[i][j]=s[k];};
 if(DELTA[i][j]>999)DELTA[i][j]=999 ;}
cout<<endl<<"Matrica DELTA"<<endl<<endl;
view(DELTA);press();
cout<<endl<<"Dispersionnaya matrica"<<endl<<endl;
viewstr(dis);


cout<<"\n"<<endl<<"Press any key to exit...";
getch();
        return 0;}



//---------------------------------------------------------------------------
void view(int L[5][5])
{
char str[] ="ABCDE";

cout<<"   | A   B   C   D   E  \n-------------------------------\n";

for(int i=0; i<=4; i++)

{cout<<" "<<str[i]<<" |";

   for(int j=0; j<=4; j++)
  if (L[i][j]==0)    cout<<"  "<<L[i][j]<<" ";
     else if (L[i][j]<100) cout<<" "<<L[i][j]<<" ";else cout<<L[i][j]<<" ";
cout<<endl;}
} ;

//---------------------------------------------------------------------------
void kw(int L_1[5][5],int L_2[5][5])
{for(int i=0; i<=4; i++)
 for(int j=0; j<=4; j++)    for(int k=0;k<=4;k++) {
 if (L_2[i][j]>(L_1[i][k]+L_1[k][j]))L_2[i][j]=(L_1[i][k]+L_1[k][j]);
 if(L_2[i][j]>999)L_2[i][j]=999 ;}
 };
//---------------------------------------------------------------------------
 void press()
 {cout<<endl<<"Press any key to continue..."<<endl;
 getch();
 };

//---------------------------------------------------------------------------
 void viewstr(char S[5][5])

{char str[]="ABCDE";

cout<<endl<<"  |A B C D E \n-----------------\n";
for(int i=0; i<=4; i++)

{cout<<" "<<str[i]<<"|";

   for(int j=0; j<=4; j++) cout<<S[i][j]<<" ";cout<<endl;}; };