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

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

Дейкстра алгоритмі - графтың төбелерін қосатын ең қысқы жолды анықтауға арналған, 1959 жылы нидерландылық ғалым Э. Дейкстра ашқан алгоритм. Бұл алгоритм программированиеде, технологиядв кең қолданылады, мысалы OSPF және IS-IS маршрутизаторлары осы алгоритм бойынша жұмыс істейді.

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

#include <iostream>

using namespace std;

const int V=6;

int *Dijkstra(int **GR, int V, int st) {

int *distance, count, index, i, u;

bool *visited;

distance = new int [V];

visited = new bool [V];

for (i=0; i<V; i++) { distance[i]=INT_MAX; visited[i]=false; }

distance[st]=0;

for (count=0; count<V-1; count++) {

int min=INT_MAX;

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

if (!visited[i] && distance[i]<=min) { min=distance[i]; index=i; }

u=index;

visited[u]=true;

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

if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&

distance[u]+GR[u][i]<distance[i])

distance[i]=distance[u]+GR[u][i];

}

return distance;

}

void main() {

int start, **GR;

GR = new int * [V];

for (int i=0; i<V; i++) GR[i] = new int [V];

int DATA[] = {

0, 1, 1, 0, 1, 0,

0, 0, 0, 1, 0, 0,

1, 0, 0, 1, 0, 0,

0, 1, 1, 0, 0, 1,

0, 0, 0, 0, 0, 1,

0, 0, 0, 0, 0, 0

};

int i,j,k=0;

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

for (j=0; j<V; j++) GR[i][j]=DATA[k++];

start=0; //начальная вершина, нумерация с 0

int *distance=Dijkstra(GR, V, start);

int m=start+1;

cout << "Стоимость пути из начальной вершины до остальных:\n";

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

if (distance[i]!=INT_MAX)

cout << m << " > " << i+1 << " = " << distance[i] << endl;

else cout << m << " > " << i+1 << " = " << "маршрут недоступен" << endl;

system("pause>>void");

}