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

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

Сред алгоритмите за решаване на тази задача за най-ефективен се счита алгоритъмът на Дейкстра, създаден през 1959 г. Тук ще се въздържим от неговото строго математическо представяне и ще се опитаме да го обясним с помощта на един пример, графа от фиг. 9. Нека да приемем, че искаме да намерим най-късите пътища от връх 0 до всички останали. Алгоритъмът се състои в следното:

• 
  регистрираме го като посетен;
  
• 
  намираме дължината на пътя от него до всеки от непосетените му съседи. Такива са върховете 1, 2 и 3, а дължината на пътя до всеки от тях са съответно 5, 8 и 16;
  
• 
  регистрираме връх 0, като предшественик на върховете 1, 2 и 3;
  
• 
  намираме най-близкия връх до началния, в случая такъв е връх 1 и разстоянието до него е 5.
  

• 
  регистрираме връх 1, като посетен;
  
• 
  намираме дължината на пътя от началния връх до непосетените съседи на връх 1, но по пътя до тях през връх 1 и:
  

• 
  за връх 3: дължината на пътя до него през връх 1 е 5+10=15. Този път е по-кратък от вече известния път 0-3 с дължина 16. Затова записваме, че дължината на най-краткият път до връх 3 е 15, и регистрираме връх 1, като предшественик на връх 3. С това връх 0 отпадна като предшественик на връх 3;
  

• 
  за връх 4: дължината на пътя до него през връх 1 е 5+7=12, за предшественик на връх 4 ще запишем връх 1.
  

• 
  намираме, че от непосетените върхове 2, 3 и 4 на най-кратко разстояние от началния връх се намира върхът 2.
  

• 
  регистрираме връх 2 като посетен;
  
• 
  намираме дължината на пътя от началния връх до непосетените съседи на връх 2, но по пътя през връх 2. Непосетен съсед на 2 е само връх 3, а дължината на пътя до връх 3 през връх 2 е 8+5=13. Пътят 0-2-3 с дължина 13 е по-кратък пътя 0-1-3 с дължина 15 и затова връх 2 ще измести връх 1 като предшественик на връх 3.
  
• 
  намираме, че от непосетените върхове 3 и 4 на по-кратко разстояние от на-чалния връх е върхът 4. Минималният път на пътя до връх 3 е с дължината 13.
  

• 
  регистрираме връх 4, като посетен;
  
• 
  намираме дължината на пътя от началния връх до непосетения съсед на връх 4, но по пътя през връх 4. Непосетен съсед на 4 е само връх 3, а дължината на пътя от началния връх до връх 3 през връх 4, т.е.пътя 0-1-4-3, е 12+6=18. Този път не е по-кратък от вече намерения път 0-2-3 с дължина 13. Новият път 0-1-4-3 няма да елиминира стария път 0-2-3, а връх 4 няма да измести връх 2 като предшественик на връх 3.
  

Препоръчваме на читателя да намери по описания алгоритъм най-кратките пътища от връх 1, 2, 3 и 4 до всички останали.

Разгледаният алгоритъм е прост и ясен.

Програмата по този алгоритъм ползва вътрешното представяне на графа (матрица на съседство или масив от списъци на съседство), за търсене съседите на поредния връх. За регистрацията на посетените върхове, предшествениците на върховете в намерените пътища и дължините на намерените пътища, ще използваме три масива: visit[], pred[] и dist[]. Тук новост е само масивът dist[]. Масивите visit[] и pred[] вече сме ползвали.

Масивът visit[] инициализираме в началото с нули, т.е. обявяваме всички върхове за непосетени, а когато посетим например i-ия връх, на visit[i] присвояваме 1.

Масивът dist[] инициализираме в началото с достатъчно голямо число, например 9999, т.е. в началото допускаме, че дължината на пътя до всеки връх е 9999 и веднага щом изчислим дължината на намерен път, например до i-ия връх, заменяме 9999 с изчислената дължина.

Масивът pred[] инициализираме с числото –1. С това допускаме, че не е известен предшественика на нито един връх. В процеса на търсенето на пътища, ако се окаже, че j-ия връх е предшественик на i-ия връх, на pred[i] присвояване стойността на j.

Следват матрицата на съседство и състоянието на трите масива след всеки преход в следващ връх за графа от фиг. 35. Те дават възможност да се проследи работата на компютърния вариант на описания по-горе алгоритъм.

0 1 2 3 4

0 0 5 8 16 0

1 5 0 0 10 7

2 8 0 0 5 0

3 16 10 5 0 6

4 0 7 0 6 0
Промените в трите масива:

i -> 0 1 2 3 4

visit-> 0 0 0 0 0

dist -> 9999 9999 9999 9999 9999

pred -> -1 -1 -1 -1 -1

j=0 visit-> 1 0 0 0 0

dist -> 9999 5 8 16 9999

pred -> -1 0 0 0 -1

j=1 visit-> 1 1 0 0 0

dist -> 9999 5 8 15 12

pred -> -1 0 0 1 1

j=2 visit-> 1 1 1 0 0

dist -> 9999 5 8 13 12

pred -> -1 0 0 2 1

j=4 visit-> 1 1 1 0 1

dist -> 9999 5 8 13 12

pred -> -1 0 0 2 1

j= 3 visit-> 1 1 1 1 1

dist -> 9999 5 8 13 12

pred -> -1 0 0 2 1

От масива dist[] се вижда, че дължината на пътя от 0-ия връх до 1-ия е 5, до 2-ия е 8, до 3-ия е 13 и до 4-ия връх е 12.

От масива pred [] се получават най-кратките пътища по следния начин:

Връх 1 има за предшественик връх 0. Следователно пътят от 0 до 1 е 0 – 1.

Връх 2 има за предшественик връх 0. Следователно пътят от 0 до 2 е 0 – 2.

Връх 3 има за предшественик връх 2, а връх 2 има за предшественик връх 0. Следователно пътят от 0 до 3 е 0 – 2 – 3.

Връх 4 има за предшественик връх 1, а връх 1 има за предшественик връх 0. Следователно пътят от 0 до 4 е 0 – 1 – 4.

Програма 5.17. Намиране най-кратките пътища в граф, представен чрез матрица на съседство, по алгоритъма на Дейкстра

#include

#include

#include

#include "graf_mat.h"

unsigned *visit, *dist,v; int *pred;

void clasGraph::dijkstra()

{

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

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

unsigned i,

t_min_dist;//Текуща минимална дистанция от стартовия връх

int j;

for (i=0;i

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

visit[v]=1;

for (i=0;i

if (A[v][i]!=0) { dist[i]=A[v][i]; pred[i]=v; }

for (;;) {

j=-1;

//Избираме като връх j този, за който visit[j]=0 и dist[j] e минимално

for (i=0;i

if (visit[i]==0 && dist[i]

if (j==-1) break;//Не е намерен непосетен на разстояние по-малко от 9999.

visit[j]=1; //Намерен е и го маркираме като посетен

//За всеки непосетен връх i изпълняваме d[i]=min(d[i], d[j]+A[j][i])

for (i=0;i

if (visit[i]==0 && A[j][i]!=0)

if ( dist[j] + A[j][i] < dist[i] ) {

dist[i]=dist[j] + A[j][i];

pred[i]=j;//Регистрираме j-ия връх като предшественик на i-ия.

}

}

}

{

if (pred[j]!=s) printPath(s, pred[j]);

}
void printResult(unsigned s)

{

unsigned i;

for (i=0;i

if (i!=s) {

if (dist[i]==9999)

cout<<"Няма път между върховете "<

else {

cout<<"Минимален път от връх "<

cout<

cout<<"\b, дължина на пътя "<

}

}

}

}
void main()

{

char ime_vh_fl[21];

cout<<"\nИме на входния файл: "; cin>>ime_vh_fl;

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); //Извежда матрицата на съседство в текст. файл

cout<<"\n"; Graph.dijkstra();

printResult(v);

}

Програма 5.18. Намиране най-кратките пътища в граф, представен чрез масив от списъци на съседство, по алгоритъма на Дейкстра

#include

#include

# include

#include "graf_sp.h"

unsigned *used,*dist, v; int *pred;

//

void clasGraph::dijkstra()

{

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

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

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

for (int i=0;i

unsigned t_min_dist;//Текуща дължина на най-късия път

int j;

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

rebro *p=a[v].first;

while (p){ i=p->nom; dist[i]=p->teg; pred[i]=v; p=p->next; }

used[v]=1;

for (;;) {

j=-1;

t_min_dist=9999;

//Избираме като връх j този, за който used[j]=0 и dist[j] e минимално

for (i=0;i

if (used[i]==0 && dist[i]

if (j==-1) break;//Няма непосетен, до който няма път.

used[j]=1; // j-ия връх е непосетен и има път до него.

//За всеки непосетен връх i изпълняваме d[i]=min(d[i], d[j]+A[j][i])

p=a[j].first;

while (p){

i=p->nom;

if (!used[i])

if (dist[i] > dist[j] + p->teg) {

dist[i]=dist[j] + p->teg;

pred[i]=j;//Регистрираме j-ия връх като предшественик на i-ия.

}

p=p->next;

}

}

}

void printPath(unsigned s, unsigned j)

{ if (pred[j]!=s) printPath(s, pred[j]); cout<
void printResult(unsigned s)

{

unsigned i;

for (i=0;i

if (i!=s) {

if (dist[i]==9999)cout<<"Няма път между върховете "<

else {

cout<<"Минимален път от връх "<cout<

cout<<"\b, дължина на пътя "<

}

}

}

}
void main()

{

char ime_vh_fl[21];

cout<<"\nИме на входния файл: "; cin>>ime_vh_fl;

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(); //Извеждаме на екрана матрицата на съседство

cout<<"\n"; Graph.dijkstra();//Намиране на най-кратките пътища

printResult(v); //Извеждане на резултата

}

Изтегляне 0.63 Mb.

Сподели с приятели: