jjool Optimal:: ma tch (string from, string to, int &dist) {

for(unsicfned i=0; i < flights.sizeO; i++) { if(flights[i].from == from &&

flights[i].to == to && !flights[i].skip)

flights[i].skip = true; предотвращает повторное использование dist = flights[i].distance; return true;

return false; не найден

Версия для метода наименьшей стоимости.

При заданном from находит самый короткий рейс.

Возвращает true, если рейс найден,

и false - в противном случае.

bool Optimal::find(string from, Flightlnfo &f)

int pos = -1;

int dist = MAXDIST; длиннее чем самый длинный рейс

for(unsigned i=0; i < flights.sizeO; i++) { if(flights[i].from == from && !flights[i].skip) {

Использует кратчайший рейс, if(flights[i].distance < dist) { pos = i;

dist = flights[i].distance;

if(pos != -1) { f = flights[pos];

flights[pos].skip = true; предотвращает повторное использование return true;

return false;

Определяет, есть ли маршрут между from и to. void Optimal::findroute(string from, string to) {

int dist; Flightlnfo f;

Проверяет, не достигнута ли цель, if(match(from, to, dist)) {

btStack.push(Flightlnfo(from, to, dist));

return;

Пробует другой рейс, if(find(from, f)) (

btStack.push(FlightInfo(from, to, f.distance));

findroute(f.to, to);

else if (!btStack.emptyO ) {

Возвращается на шаг назад и проверяет другой рейс. F = btStack. top О ; btStack.popO; findroute(f.from, f.to);

Находит оптимальное решение, используя метод наименьшей стоимости с удалением пути, int main О {

char to[40], from[40];

Optimal ob;

Добавляет информацию о рейсах в базу данных.

ob.addflight( New York , Chicago , 900); i

ob.addflight( Chicago , Denver , 1000);

Ob.routeO ;

Выводит оптимальное решение. ob.showOptO ;

return 0;

Далее приведен вывод профаммы. From? New York o? Los Angeles

New York to Chicago to Denver to Los Angeles Distance is 2900

оЪ.addf1ight( New York , Toronto , 500); ob.addflight( New York . Denver , 1800); ob.addflight( Toronto , Calgary , 1700); ob.addflight( Toronto , Los Angeles , 2500); ob.addflight( Toronto , Chicago , 500); ob.addflight ( Denver, Urbana , 1000); ob.addflight( Denver , Houston , 1000); ob. addf1ight( Hous ton , Los Angeles , 1500); ob.addflight( Denver , Los Angeles , 1000);

Получает пункты оправления и назначения, cout From? ;

cin.getline(from, 40); cout To? ;

cin.getline(to, 40);

Находит множественные решения. for(;;) {

Проверяет, есть ли решение.

ob.findroute(from, to);

Если ни один маршрут не найден, завершается, if(!ob.routefound()) break;