Нахождение кратчайшего пути в графе

        j = 0;

        way[0] = toNode;

        currNode = toNode;

for ( k = N - 2; k >= 0; k-- ) {

            if ( minWeights[currNode][k] != minWeights[currNode][k + 1] ) {

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

if ( minWeights[i][k] + wm[i][currNode] == minWeights[currNode][k + 1] ) {

                        j++;

way[j] = i;

                        currNode = i;

                        break;

                    }

                }

}

        }

        *length = j;

}

return way;

}

int main() {

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

int i, j;

string from, to;

int f,t;

int *way;

int length, weight;

string g[N];

Initial(g);

int w[N][N]={0  ,250,-1 ,320,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,

250,0  ,300,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,

-1 ,300,0  ,-1 ,-1 ,-1 ,423,-1 ,-1 ,-1 ,-1 ,-1 ,

320,-1 ,-1 ,0  ,640,412,830,-1 ,-1 ,-1 ,-1 ,-1 ,

-1 ,-1 ,-1 ,640,0  ,-1 ,-1 ,550,-1 ,-1 ,-1 ,-1 ,

-1 ,-1 ,-1 ,412,-1 ,0  ,-1 ,300,-1 ,-1 ,-1 ,-1 ,

-1 ,-1 ,423,830,-1 ,-1 ,0  ,520,540,580,-1 ,-1 ,

-1 ,-1 ,-1 ,-1 ,550,300,520,0  ,-1 ,430,280,-1 ,

-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,540,-1 ,0  ,400,-1 ,-1 ,

-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,580,430,400,0  ,-1 ,650,

-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,280,-1 ,-1 ,0  ,360,

-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,650,360,0 };

cout << "Список городов, обслуживаемых компанией :" << endl << endl;

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

cout<<g[i]<< endl;

}

cout << endl;

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

for (j = 0; j < i; j++) {

        if (w[i][j]>0) {

cout << g[i] << " - " << g[j] << "  " << w[i][j] << " км "  << endl;

 }

}

}

cout << endl;

cout << "Введите исходный город: ";

cin >> from;

cout << "Введите пункт назначения: ";

cin >> to;

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

if (g[i]==from) f=i;

if (g[i]==to) t=i;

}

way = minimalLengthWay( w, f, t, &length, &weight );

if ( way[0] == -1 )

cout << "Невозможно приготовить маршрут !";

else {

for ( i = length; i >= 0; i-- ){

if ( i != length ) cout << " -> ";

cout << g[way[i]];

}

cout << "\nДлина пути: " << weight << endl << endl;

}

system("Pause");

return 0;

        Приложение В. Список литературы

 

1. Шилдт Герберт «Си ++. Руководство для начинающих, 2е издание», М.; Издательский дом «Вильямс», 2005 г.
2. Кубенский А. А. «Структура и алгоритмы обработки данных: объектно - ориентированный подход и реализация на Си ++», Спб.; БХВ-Петербург, 2004 г.
3. Седжвик Роберт «Фундаментальные алгоритмы на Си++», К.; Издательство «ДиаСофт», 2001 г.
4. Уильям Топп, Уильям Форд «Структуры данных в Си ++», М.; ЗАО «Издательство БИНОМ», 1999 г.