დეიქსტრას ალგორითმი (Dijkstra's Algorithm) C++

ეს ალგორითმი გამოთვლის რომელი მაშრუტებით მივალთ ყველაზე იაფად თბილისიდან სანდიეგომდე მოცემული ნახაზის მიხედვით:

// ConsoleApplication4.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

using namespace std;

#define  N 10

int _tmain(int argc, _TCHAR* argv[])

{

int a[N][N] =

{

{ 0, 500, 400, 450, 700, 0, 0, 0, 0, 0 },  //tbilisi

{ 500, 0, 0, 0, 0, 700, 800, 750, 0, 0 },  //munich

{ 400, 0, 0, 0, 250, 550, 550, 600, 0, 0 },  //Amsterdam

{ 450, 0, 0, 0, 0, 800, 0, 850, 850, 0 },  //istambul

{ 700, 0, 250, 0, 0, 500, 0, 0, 0, 0 },  //Rome

{ 0, 700, 0, 550, 500, 0, 0, 0, 0, 550 },  // New Yourk

{ 0, 800, 550, 0, 0, 0, 0, 0, 0, 350 },  //Huston

{ 0, 750, 600, 0, 0, 0, 0, 0, 350, 450 }, //Chikago

{ 0, 0, 0, 850, 0, 0, 0, 350, 0, 250 },  //Los Angeles

{ 0, 0, 0, 0, 0, 550, 350, 450, 250, 0 }  //San Diego

};

int d[N] = { 0, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }; //2000000000 eseni aviget usasrulobis magivrad

int b[N] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; //chartulia tuara qalaqi; roca metia xo irtveba; tavidan yvela chartulia

for (int p = 0; p < N - 1; p++)

{

int i;

int k = -1;

int min = 2000000001;

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

if (b[i] != 0 && d[i] < min)//chartuli iyos da naklebi minimumze

{

k = i; min = d[i]; // es iqneba minimumi

}

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

if (b[i] != 0 && a[k][i]>0) //tu metia 0ze eseigi aris mimosvla, tan chartuliq// a[k][i] es aris dashoreba //minimumshi sadac vart imas davumatet dashorebebi

{

int h = d[k] + a[k][i];

if (h < d[i])

d[i]=h; //tu naklebi gamovid mashin gadavawerot

}

b[k] = 0; // gatishva is romlebtanac shevamowmet yvelaperi// gadavalt imaze romlebdic chartulebia da iq vezebt minimums

}

cout << d[N - 1] << endl;

system("pause");

return 0;

}