Намиране най-кратък път от зададен връх до всички други върхове в безтегловен граф

5.7.Намиране най-кратък път от зададен връх до всички други върхове в безтегловен граф

Между два върха може да има много пътища, само един път или изобщо да няма път. Когато има много пътища, най-кратък е този, който включва най-малко върхове.

Алгоритъм за намиране най-кратък път между два върха в безтегловен граф можем да създадем като използваме алгоритъма за обхождане в ширина, тъй като то е обхождане по нива.

Н
ека да си поставим задачата да намерим най-краткия път от 0-ия връх до някой друг връх от графа, показан на фиг. 34. За целта ще обходим графа в ширина, като започнем от 0-ия връх, който е на 0-во ниво.

Фиг. 34. Намиране на най-кратък път в безтегловен граф

На първо ниво са всички непосетени върхове (1, 2, 3 и 7), съседи на 0-ия връх. На тях 0-ия връх е предшественик и на фиг. 34 това е показано с нулите, изписани извън кръгчетата на тези върхове.

На второ ниво са върховете 4 и 5, като непосетени съседи на върха 1, и връх 8, като непосетен съсед на 7.

На трето ниво е само връх 6 и негов предшественик е върхът 4.

Сега вече можем да намерим най-краткия път от 0-ия връх до всеки от останалите. Например най-краткия път от 0-ия 6-ия връх ще намерим по следния начин:

• 
  изпращаме в стек: крайния връх, т.е. връх 6, неговия предшественик, т.е. връх 4, предшественика на връх 4, т.е. връх 1, предшественика на връх 1, т.е. връх 0. Тъй като 0-ия връх нама предшественик, той е началния връх. В стека, от върха към дъното, се намират върховете: 0, 1, 4 и 6
  
• 
  вземаме върховете от стека и ги записваме в редицата, образуваща пътя от 0-ия 6-ия връх. Ще получим, че търсеният път е редицата 0, 1, 4 и 6.
  

Следват две програми за намиране на най-кратък път в безтегловен граф.

# include

# include

#include "graf_mat.h"

void clasGraph::kraBFS()

{

unsigned i,j,

kv, //Краен връх

v, //Tекущ връх

*visit; //Масив, отчитащ посетеността на върховете

int* pred; //Масив с предшествениците на върховете при обхождането

if (!(visit=new unsigned[BrV])) exit(0);

if (!(pred=new int[BrV])) exit(0);

for (i=0;i

fout.open("DopInf",ios::ate);

fout<<"\nСъдържание на масива на предшествениците след поредна стъпка:\n";

cout<<"Начален връх: "; cin>>nv;

cout<<"Краен връх: "; cin>>kv;

Opashka.DobEl(nv);//Добавяме към опашката стартовия елемент

visit[nv]=1;

while (Opashka.Br>0) {//Докато опашката не е празна ...

Opashka.VzeEl(v); //... вземаме поредния връх от опашката,...

//...добавяме към опашката необходените му наследници,...

//...отбелязваме ги, като обходени, и записваме предшественика им.

for (j=0;j

if (A[v][j]==1 && visit[j]==0) {pred[j]=v;visit[j]=1;Opashka.DobEl(j);}

for (j=0;j

for (j=0;j

}

if (pred[kv]==-1) {cout<<"Не e намерен път!\n"; getch();return;}

//по следния начин: изпращаме в стека крайния връх, изпращаме там неговия

//предшественик и т.н. докато изпратим там и началния връх. След това вземаме

//върховете от стека и ги извеждаме на екрана. Изведената редица е пътят.

Stek.DobEl(kv);

v=kv;

unsigned L=Stek.Br; //Дължина на пътя

//Извеждане на получения път на екрана

cout<<"Най-кратъкиЯт път от връх "<

while (Stek.Br) {Stek.VzeEl(v); cout<

cout<<"\b, дължината му е "<

fout.close();

}
void main()

{

char ime_vh_fl[21];

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвеждаме от текстовия файл броя на върховете на графа

clasGraph Graph; //Създава обекта Graph

Graph.make_graf(); //Запълва матрицата на съседство

Graph.display_graf(); //Извежда матрицата на съседство на екрана

Graph.display_graf(fout); //Извежда матр. на съседство в текст.файл

Graph.kraBFS(); //Намира и извежда най-краткия път

cout<<"\nДопълнителна информация можете да намерите във файл DopInf.\n";

}
Програма 5.14. Намиране на най-кратък път между два върха в безтегловен граф, представен с масив от списъци на съседство

# include

# include

# include "graf_sp.h"

//Функция за обхождане в ширина от даден връх, модифицирана да запомня на предшественика на всеки връх

void clasGraph::kraBFS()

{

unsigned i,j,

kv, //Краен връх

v, //Tекущ връх

*visit;// Масив, отчитащ посетеността на върховете

int* pred;// Масив с предшествениците на върховете при обхождането

rebro *p; // Указател към обект ребро

if (!(visit=new unsigned[BrV])) exit(0);

if (!(pred=new int[BrV])) exit(0);

for (i=0;i

fout.open("DopInf",ios::ate);

fout<<"\n//Mасивът на предшествениците след поредна стъпка:\n";

cout<<"Начален връх: "; cin>>nv;

cout<<"Краен връх: "; cin>>kv;

Opashka.DobEl(nv);//Добавяме към опашката началния елемент

visit[nv]=1;

while (Opashka.Br>0) {//Докато опашката не е празна ...

Opashka.VzeEl(v);//... вземаме поредния връх от опашката ...

p=a[v].first;

while (p){

//...и добавяме към опашката необходените му наследници,...

//...отбелязваме ги, като обходени, и записваме предшественика им.

j=p->nom;

if (!visit[j]) {Opashka.DobEl(j); visit[j]=1; pred[j]=v;}

p=p->next;

}

for (j=0;j

for (j=0;j

}

if (pred[kv]==-1) {cout<<"Не e намерен път!\n"; getch();return;}

//по следния начин: изпращаме в стека крайния връх, изпращаме там неговия

//предшественик и т.н. докато изпратим там и началния връх. След това вземаме

//върховете от стека и ги извеждаме на екрана. Изведената редица е пътят.

Stek.DobEl(kv);

v=kv;

unsigned L=Stek.Br;

//Извеждане на получения път на екрана

cout<<"Най-кратъкият път от връх "<

while (Stek.Br) {

Stek.VzeEl(v); cout<

}

cout<<"\b, дължината му е "<

fout.close();

}
void main()

{

char ime_vh_fl[21];

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвеждаме от текстовия файл броя на върховете на графа

clasGraph Graph; //Създава обекта Graph

Graph.make_graf(); //Запълва матрицата на съседство

Graph.display_graf(); //Извежда матрицата на съседство на екрана

Graph.display_graf(fout);//Извежда матрицата на съседство в текст. файл

Graph.kraBFS(); //Намира и извежда най-краткия път

cout<<"\nДопълнителна информация можете да намерите във файл DopInf.\n";

}