Переменные:
const char file[]="c:\\Goroda.txt" - имя файла на жестком диске, хранящим названия городов.from, to - начальная и конечная точки маршрута.w[N][N] - весовая матрица графа.g[N] - массив, хранящий список городов.*way - динамический массив для хранения маршрута.
Функции:
void Initial(string *Arr) - используется в программе для заполнения массива string g[] списком городов из файла file.
int *minimalLengthWay(int wm[N][N], int fromNode, int toNode, int *length, int *weight) - находит кратчайший путь в графе
Описание работы программы
После запуска программы на экран выводится список городов и расстояния между ними. Нужно будет ввести город отправления и город назначения.
После работы программы, на экране появится маршрут следования и длина пути.
Тестирование программы
Вывод список городов
Вывод расстояний между городами
Ввод данных
Вывод результата
Список литературы
. Шилдт Герберт «Си ++. Руководство для начинающих, 2-е издание», М.; Издательский дом «Вильямс», 2005 г.
. Кубенский А. А. «Структура и алгоритмы обработки данных: объектно-ориентированный подход и реализация на Си ++», Спб.; БХВ-Петербург, 2004 г.
. Седжвик Роберт «Фундаментальные алгоритмы на Си++», К.; Издательство «ДиаСофт», 2001 г.
4. Уильям Топп, Уильям Форд «Структуры данных в Си ++», М.; ЗАО «Издательство БИНОМ», 1999 г.
Приложение А
Схема алгоритма
Приложение Б
Листинг программы
#include <iostream.h>
#include <stdio.h>
#include <string>
#include <fstream.h>
#include <windows.h>
#define N 12char file[]="c:\\Goroda.txt";Initial(string *Arr) {fin;.open(file);(fin==NULL)
{<<"Error open file";("Pause");(1);
}n=0;>>Arr[n];(fin.good())
{++;>>Arr[n];
}.close();
}*minimalLengthWay(int wm[N][N], int fromNode, int toNode, int *length, int *weight){ **minWeights; // Для хранения фронта волны
|
|
int i, j, k;
int *way; // Для хранения найденного пути и уже однажды пройденных вершин
bool find;tempLength;currNode;= new int*[N];(i = 0; i < N; i++) {[i] = new int[N];
}= new int[N];(i = 0; i < N; i ++)(j = 0; j < N; j ++)[i][j] = -1;(i = 0; i < N; i ++)[i] = -1;(i = 0; i < N; i ++)[fromNode][i] = 0;= false;(k = 0; k < N - 1; k ++) {(i = 0; i < N; i ++) {= minWeights[i][k];(j = 0; j < N; j++) {(minWeights[j][k]!= -1 && wm[j][i]!= -1) {((tempLength!= -1 && tempLength > minWeights[j][k] + wm[j][i]) || tempLength == -1) {= minWeights[j][k] + wm[j][i];
}
}
}[i][k+1] = tempLength;
}
}= minWeights[toNode][N-1]!= -1; // проверяем найден ли какй-либо путь(find) *weight = minWeights[toNode][N-1]; (find) { // если путь найден - вычисляем его но в обратной последовательности
j = 0;[0] = toNode;= toNode;(k = N - 2; k >= 0; k--) {(minWeights[currNode][k]!= minWeights[currNode][k + 1]) {(i = 0; i < N; i ++) {(minWeights[i][k] + wm[i][currNode] == minWeights[currNode][k + 1]) {++;[j] = i;= i;;
}
}
}
}
*length = j;
}way;
}main() {(1251);(1251);i, j;from, to;f,t;*way;length, weight;g[N];(g); w[N][N]={0,250,-1,320,-1,-1,-1,-1,-1,-1,-1,-1,
,0,300,-1,-1,-1,-1,-1,-1,-1,-1,-1,
,300,0,-1,-1,-1,423,-1,-1,-1,-1,-1,
,-1,-1,0,640,412,830,-1,-1,-1,-1,-1,
,-1,-1,640,0,-1,-1,550,-1,-1,-1,-1,
,-1,-1,412,-1,0,-1,300,-1,-1,-1,-1,
,-1,423,830,-1,-1,0,520,540,580,-1,-1,
,-1,-1,-1,550,300,520,0,-1,430,280,-1,
,-1,-1,-1,-1,-1,540,-1,0,400,-1,-1,
,-1,-1,-1,-1,-1,580,430,400,0,-1,650,
,-1,-1,-1,-1,-1,-1,280,-1,-1,0,360,
,-1,-1,-1,-1,-1,-1,-1,-1,650,360,0 };
cout << "Список городов, обслуживаемых компанией:" << endl << endl;
for (int i = 0; i < N; i++) {<<g[i]<< endl;
}<< endl;(int i = 0; i < N; i++) {(j = 0; j < i; j++) {(w[i][j]>0) {<< g[i] << " - " << g[j] << " " << w[i][j] << " км " << endl;
}
}
}
cout << endl;
cout << "Введите исходный город: ";
cin >> from;
cout << "Введите пункт назначения: ";
cin >> to;(i = 0; i < N; i++) {(g[i]==from) f=i;(g[i]==to) t=i;
}= minimalLengthWay(w, f, t, &length, &weight); (way[0] == -1)
cout << "Невозможно приготовить маршрут!";
else {(i = length; i >= 0; i--){(i!= length) cout << " -> ";<< g[way[i]];
|
|
}<< "\nДлина пути: " << weight << endl << endl;
}("Pause");0.