Графтың бір төбесінен екінші төбесінің ең қысқа жолын табатын Флойд-Уоршелл алгоритмін сипаттаңыз

Граф дегеніміз – төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы. Графтың екі төбесінің арасындағы ара қашықтық деп екі төбені қосатын ең қысқа жолды айтады. a және b төбелерінің ара қашықтығы d(a,b) арқылы белгіленеді. Графта a және b-ны қосатын жол жоқ болса, яғни бұл төбелер әр түрлі орамдылық компонентіне тиісті болса, онда екі төбе арасындағы ара қашықтық шексіз боп саналады. Осы графтың төбелерін қосатын ең қысқы жолды Флойд-Уоршелл алгоритмінің көмегімен табуға болады.

Флойд-Уоршелл алгоритмі - графтың төбелерін қосатын ең қысқы жолды анықтауға арналған, 1962 жылы Роберт Флойд пен Стивен Уоршелл ұсынған алгоритм. Дейкстра алгоритміне қарағанда Флойд-Уоршелл алгоритмі оң және теріс салмақты граф қабырғаларында да жүзеге асырыла алады.

Программасы:

#include <iostream.һ>

using namespace std;

const int maxV=1000;

int i, j, n;

int GR[maxV][maxV];

//алгоритм Флойда-Уоршелла

void FU(int D[][maxV], int V)

{

int k;

for (i=0; i<V; i++) D[i][i]=0;

for (k=0; k<V; k++)

for (i=0; i<V; i++)

for (j=0; j<V; j++)

if (D[i][k] && D[k][j] && i!=j)

if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)

D[i][j]=D[i][k]+D[k][j];

for (i=0; i<V; i++)

{

for (j=0; j<V; j++) cout<<D[i][j]<<"\t";

cout<<endl;

}

}

//басты функция

void main()

{

setlocale(LC_ALL, "Rus");

cout<<"Graftagy tobeler sany= "; cin>>n;

cout<<"Kabyrgalar salmagynyn matricasyn engiziniz=\n";

for (i=0; i<n; i++)

for (j=0; j<n; j++)

{

cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";

cin>>GR[i][j];

}

cout<<"Kyska zhol matricasy="<<endl;

FU(GR, n);

system("pause>>void");

}