Давыдов В.Г. - Программирование и основы алгоритмизации - 2003
.pdfных путей). Нас при поиске оптимального пути интересует на каж дом этапе только один путь, а не все сразу, т.е. требуется последова тельный перебор путей. Из информации на рис. 83 следует, что для перебора путей хорошо подходит рекурсивный алгоритм (аналогия с вычислением факториала).
р,
Вершина
Путь
Ребро •
Рис. 83. Рекурсивный перебор путей
16.4. Представление кратчайшего пути до каждой вершины
Сведения о любом пути должны содержать следующую ин формацию.
1.Имеется ли путь до вершины графа?
2.Суммарный вес пути, начиная от заданной начальной вер шины (start)?
Но только этих сведений недостаточно, так как нет указаний, откуда и как двигаться. Для задания недостающих сведений можно организовать линейный список, который для графа, представленно го выше на рис. 81, будет иметь вид, показанный на рис. 84 а. Такой линейный список можно организовать на базе массива структур (рис. 84 б).
stmjct W |
|
|
// |
Путь |
до |
одной |
вершины |
|
|
|||
{ |
int |
|
exist; |
// |
(!= |
0) - |
|
путь |
имеется |
|
|
|
|
|
|
|
|
||||||||
|
|
ref; |
// |
Предыдущая |
вершина^ |
|
через |
|
||||
|
±nt |
|
|
|
||||||||
|
|
|
// |
которую |
проходит |
путь |
|
|||||
|
float |
|
SumDlst; |
пути |
||||||||
|
|
// |
Суммарная |
|
длина |
минимального |
||||||
} |
; |
|
|
|
|
|
|
|
|
|
|
|
// |
Адрес |
первого |
элемента |
массива |
с |
информацией |
о |
минимальном |
||||
// |
пути |
между |
заданными |
|
вершинами |
|
|
|
|
|
|
|
W |
|
*pMinWay/ |
|
|
|
|
|
|
|
|
|
|
270
start |
|
|
finish |
|
start |
finish |
|
|
5 |
1 |
4 |
5 |
2 |
|
1 |
2 |
3 |
4 |
|
1 |
1 |
1 |
1 |
exist |
1 |
1 |
1 |
1 |
1 |
0.0 |
10.0 |
20.0 |
30.0 |
SumDist |
0.0 |
30.0 |
30.0 |
10.0 |
20 0 |
0 |
1 |
4 |
5 |
ref |
0 |
5 |
4 |
1 |
4 |
J |
t |
i |
(REFerencet- ссылка): 0 - конец списка |
||
a) |
|
6) |
Рис. 84. Представление кратчайшего пути между вершинами: а) с помощью линейного списка;
б) на базе массива структур
16.5.Как найти минимальный путь
16.5.1.Требуется ли полный перебор путей
При поиске минимального пути часть путей можно отбросить (рис. 85). Попытки, представленные на этом рис., неуместны, если, допустим, существует
pMinWayf 18 ].SumDist |
= 50.0 и pMinWayf 18 ].exist |
!= О |
Текущий путь длиной 200.0 |
finish |
•в;.-; |
• о |
Рис. 85. Поиск минимального пути
16.5.2. Организация перебора путей
Как уже указывалось, для этой цели хорошо подходит рекур сивный алгоритм. Рассмотрим, как можно пройти отрезок пути от достигнутой промежуточной вершины (intermediate) до финиша (fin ish) - рис. 86.
271
start |
О • |
О |
intermediate |
finish |
|
а) intermediate = finish |
Вершина |
Конец |
|
||
б) intermediate != finish |
|
|
intermediate |
Путь |
|
•>\ Ребро |
|
Рис. 86. Прохождение пути от достигнутой вершины до финиша
Попытку шага вперед из достигнутой вершины по заданному ребру будем делать с помощью функции ForStep, а прохождение пу
ти (если он есть) от достигнутой вершины до вершины finish |
- с по |
|
мощью функции Pass Way (взаимно |
рекурсивный вызов PassWay - |
|
For Step). |
|
|
Для решения транспортной задачи спроектируем программу и |
||
в ней разработаем функции PassWay |
-ForStep. Спецификация |
функ |
ции, выполняющей шаг вперед, представлена на рис. 87. Обратите внимание, что в список параметров этой функции включены только
три параметра - topl^ |
IndArc, top2. |
Это важно, |
так как для |
|||
рекурсивных |
функций, |
как это |
было |
показано |
выше, |
число |
параметров |
следует минимизировать. |
Поэтому Gr, pMinWay |
опре |
|||
делены как глобальные объекты. Исходный текст программы для решения транспортной задачи, включающий определение функции ForStep., приведен ниже. На данном этапе в этом тексте рекомендуем рассмотреть только введенные типы, данные и определения всех
функций, кроме solution |
и PassWay. |
Указанные в конце функции бу |
|||
дут рассмотрены позже. |
|
|
|
|
|
Достигнутая вершина |
|
int top1 |
- |
|
|
Индекс ребра, по которому |
|
ForStep |
W *pMin\/Vay |
||
шагаем |
|
int IndArc- |
|||
|
Массив с инфор |
||||
Вершина на конце ребра int top2 |
- |
|
|||
Граф |
GRAPH |
Gr- |
|
мацией о наилуч |
|
|
|
|
|
|
шем пути |
input |
|
|
|
process |
output |
Рис. 87. Спецификация функции, выполняющей шаг вперед по ребру
Обратите также внимание на то, что функция ForStep является служебной функцией и вызывается из функции PassWay, которая, в свою очередь, вызывается из функции solution.
Ill
|
Файл |
TestGr.cpp. |
Тестирование |
|
решения |
транспортной |
задачи |
||||||||
с размещением |
данных в |
динамической |
памяти. |
транспортной |
|||||||||||
|
Определение |
|
функций^ |
используемых |
при |
решении |
|||||||||
задачи, |
приведено |
в |
файле |
Graph.срр. |
|
в |
динамической |
|
памя |
||||||
ти |
Определение |
|
Функций |
размеш,ения |
|
данных |
|
|
|||||||
и освобождения |
занятой |
динамической |
|
памяти находится |
в |
||||||||||
файле |
GrAlocFree.срр. |
|
|
|
проекта |
находится |
в |
файле |
|||||||
|
Включаемый |
файл |
программного |
|
|||||||||||
GrHead.h. |
|
|
Консольное |
приложение, |
Visual C-f-f- |
6 |
|
|
|||||||
V |
Давыдов В.Г. |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/ / |
Включаемый |
файл |
программного |
проекта |
|
для |
решения |
|
|
||||||
//транспортной задачи
^include "GrHead.h"
±nt |
main |
( |
|
|
|
|
// |
Возвраш,ает |
О при |
успехе |
|
||
|
±пЬ |
|
|
|
АгдС, |
|
// |
Число |
аргументов |
в |
командной |
||
|
cha.r |
|
|
|
*ArgV[ |
] ) |
// |
строке |
|
на |
аргументы |
||
|
|
|
|
/ |
/ Массив указателей |
||||||||
|
|
|
|
|
|
|
// |
командной |
строки |
|
|
||
{ |
// Проверка |
числа |
аргументов |
командной |
строки |
|
|||||||
|
|
||||||||||||
|
±f( |
ArgC |
/= |
3 ) |
|
|
|
|
|
|
|
|
|
|
{ |
printf( |
|
|
|
|
|
|
|
|
|
|
|
"\п |
|
В |
командной |
строке |
должно быть |
три |
аргумента: |
||||||
Ошибка |
5. |
||||||||||||
"\п |
Имя__проекта. |
ехе |
имя_файла_ввода |
имя_файла_вывода |
\п" ) , |
||||||||
|
|
exit |
( |
5 |
) ; |
|
|
|
|
|
|
|
|
}
//Чтение информации о графе
ReadGraph ( ArgV[ 1 ] ) ;
//Печать информации о графе
|
WriteGraph( |
ArgV[ |
|
2 ], |
"w" ) |
; |
|
|
|
|
|
||||
|
solution |
|
( ) |
; |
|
// |
|
Решение |
транспортной |
задачи |
|||||
|
// |
Вывод |
результатов |
решения |
|
|
|
|
|
|
|||||
|
OutRes ( |
ArgV[ 2 |
], |
"а" |
) |
; |
|
|
|
|
|
|
|||
} |
•returri |
Or |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
лов, |
Файл |
GrHead.h. |
Подключение |
стандартных |
заголовочных |
фай |
|||||||||
объявление |
используемых |
|
структурных |
типов, |
|
объявление |
|||||||||
объектов |
с |
описателями |
класса |
хранения |
"внешний" |
и прототипов |
|||||||||
функций. |
Используется |
|
как |
заголовочный |
файл |
в |
программном |
||||||||
проекте |
для |
|
решения |
транспортной |
задачи |
(задачи |
коммивояже |
||||||||
ра) . |
|
В.Г. |
Консольное |
приложение. |
Visual |
C++ 6 |
|
||||||||
|
Давыдов |
|
|||||||||||||
273
_v
// Предотвращение |
возможности |
многократного |
подключения |
|||||
iifndef |
GRHEAD_H |
|
|
|
|
|
||
^define |
|
GRHEAD Н |
|
|
|
|
|
|
^include |
|
<stdio.h> |
// |
Для |
exit |
ввода-вывода |
|
|
^include |
|
<stdlib.h> |
// |
Для |
( ) |
|
||
//Структурный тип для ребра графа
stjnzct |
А |
|
|
|
|
|
{ |
|
first/ |
// |
1-я |
вершина |
ребра |
±nt |
|
|||||
±nt |
|
last; |
// |
2-я |
вершина |
ребра |
£1олt |
weight; |
// |
Вес |
ребра |
|
|
} ;
//Структурный тип для графа
strvLcb GRAPH
{ |
±nt |
NumTop; |
// |
Число |
вершин |
|
|
|
|||||
|
|
|
|
||||||||||
|
±nt |
NumArc; |
// |
Число |
ребер |
начало |
массива |
ребер |
|||||
|
A |
*pArc; |
// |
Указатель |
на |
||||||||
}; |
|
|
|
|
// |
в |
динамической |
памяти |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Структурный |
тип пути |
до одной |
вершины |
|
|
|||||||
struct |
W |
|
|
|
|
|
|
|
|
|
|
|
|
{ |
int |
exist; |
|
// |
(!=0) |
|
в |
графе |
имеется путь |
||||
|
|
|
|||||||||||
|
|
|
|
|
// |
|
|
до |
|
вершины |
|
|
|
|
xnt |
ref; |
|
// |
Предыдущая |
вершина, |
через |
которую |
|||||
|
|
|
|
|
// |
проходит |
путь |
до |
данной |
вершины |
|||
|
£loa,t |
SumDlst; |
// |
Суммарная |
длина |
минимального |
пути |
||||||
}. |
|
|
|
|
// |
до |
данной |
|
вершины |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Объявления |
внешних |
|
объектов |
|
|
|
|
|
|
|||
extern |
GRAPH |
|
// |
Граф |
|
|
|
|
|
|
|
||
// |
Указатель |
Gr; |
массив |
|
для |
хранения |
информации о |
||||||
на |
|
структур |
|||||||||||
// |
|
минимальном |
пути |
от start |
до |
|
finish |
|
|
|
|||
extern |
W |
*pMlnWay; |
// |
Вершина |
- |
финиш |
пути |
|
|||||
extern |
int |
finish; |
|
|
|||||||||
extern |
int |
start; |
|
// |
Вершина |
- старт |
пути |
|
|||||
//Прототипы функций
void |
GrAllocDM( |
void, |
) ; |
|
|
|||
void |
GrFreeDM( |
void |
|
) ; |
) |
; |
||
void |
ForStep |
( |
int, |
int, |
int |
|||
void |
PassWay |
( |
int |
) ; |
) |
; |
|
|
void |
solution |
|
( void |
*, |
|
|
||
void |
OutRes |
( char* |
char |
*pMode ) ; |
||||
void |
ReadGraph |
( char |
|
*pFlleInp |
) ; |
|||
274
|
void |
|
WriteGraph |
( char |
^pFileOut, |
char |
*pMode |
) ; |
|
|||||
^endif |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Файл |
GrInpOut.срр. |
Функции |
файлового |
чтения |
данных о |
графе |
|||||||
и печати |
их. |
|
в |
программном |
проекте |
для |
решения |
транспорт |
||||||
ной |
Используется |
|
||||||||||||
задачи |
(задачи |
коммивояжера) . |
|
|
|
|
|
|
||||||
V Давыдов |
В.Г, |
|
Консольное |
приложение. |
Visual |
C++ 6 |
|
|||||||
// Включаемый |
файл |
программного |
проекта |
для |
|
решения |
|
|||||||
// |
транспортной |
задачи |
(задачи |
коммивояжера) |
|
|
||||||||
#include |
|
"GrHead,h" |
|
|
|
|
|
|
|
|
||||
// |
Чтение |
данных |
о |
графе |
|
|
|
|
|
|
|
|
||
void |
ReadGraph |
( |
|
|
|
|
|
|
|
|
|
|
||
|
// |
Указатель |
на файл |
данных |
|
|
|
|
|
|
||||
{ |
char |
|
|
"^pFilelnp |
) |
|
|
|
|
|
|
|
||
FILE |
|
|
*pStrInp; |
// Указатель на структуру |
со |
|
||||||||
|
|
|
|
|||||||||||
|
±пЬ |
|
|
|
i , |
|
// |
сведениями |
о |
файле |
ввода |
|
||
|
|
|
|
|
// Индекс |
ребра |
|
|
fscanf( |
) |
||||
|
|
|
|
RetCode, |
// Возвращаемые |
значения |
||||||||
//или их сумма
RetCodel; |
// Возвращаемое |
значение |
fclose( |
) |
//Открытие файла ввода
pStrlnp |
= fopen( |
pFilelnpr |
|
"г" |
) |
; |
|
|
|
|
||||
±£( |
pStrlnp |
|
== NULL |
) |
|
|
|
|
|
|
|
|
||
{ |
printf( |
|
|
"\n |
Ошибка |
50, |
Файл |
%s для |
чтения |
не " |
|
|||
|
|
|
|
|||||||||||
|
|
|
|
"открыт |
\п", |
pFilelnp |
|
) ; |
|
|
|
|||
|
exit |
( |
50 |
) ; |
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Чтение |
количества |
вершин |
и |
количества |
ребер |
|
|||||||
RetCode |
= |
fscanf( |
pStrlnp, |
|
" %d", |
&Gr,NumTop |
) ; |
|
||||||
±f( |
RetCode |
|
!= 1 |
) |
|
|
|
|
|
|
|
|
|
|
( |
printf |
|
( |
"\n |
Ошибка |
60, |
Ошибка |
при |
чтении |
числа |
" |
|||
|
|
|||||||||||||
|
|
|
|
"верш^^н |
графа |
\п" |
) ; |
|
|
|
|
|
||
|
exit |
( |
60 |
) ; |
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
RetCode |
= |
fscanf |
( pStrlnp, |
" |
%d", |
&Gr,NumArc |
) ; |
|
||||||
±f( |
RetCode |
|
1=1) |
|
|
|
|
|
|
|
|
|
||
{ |
printf |
|
( |
"\n |
Ошибка |
70, Ошибка |
при |
чтении |
числа |
" |
||||
|
|
|||||||||||||
|
|
|
|
"ребер |
графа |
\п" |
) ; |
|
|
|
|
|
||
|
exit |
( |
70 |
) ; |
|
|
|
|
|
|
|
|
|
|
}
275
// Размещение |
структур |
данных |
графа |
в |
динамической |
памяти |
||||||||||
GrAllocDM( |
) |
; |
|
|
|
|
|
|
|
|
|
|
|
|
||
// |
Заполнение |
массива |
ребер |
графа |
|
|
|
|
|
|
||||||
Ret |
Code |
= |
0; |
1 < Gr.NumArc; |
|
i + -h ) |
|
|
|
|
|
|
||||
£ою ( i |
= 0; |
|
|
|
|
|
|
|
||||||||
{ |
RetCode |
|
+= fscanf( |
pStrlnp, |
|
" |
%d %d |
%g", |
|
|
||||||
|
|
|
1 |
J.last, |
||||||||||||
|
|
|
|
&Gr.pArc[ |
i |
].first, |
|
|
&Gr.pArc[ |
|||||||
|
±f( |
( |
|
&Gr.pArc[ |
1 |
].weight |
) |
) |
; |
|
|
|
||||
|
Gr.pArcl |
i |
].first |
|
< |
0 |
\\ |
|
) |
| | |
|
|||||
|
|
( |
Gr.pArcl |
i |
].first |
|
>= Gr.NumTop |
|
||||||||
|
|
( |
Gr.pArc[ |
i |
].last |
|
< |
0 |
) |
|
\\ |
|
) ) |
|
|
|
|
|
( |
Gr.pArcf |
1 |
].last |
|
>= |
Gr.NumTop |
|
|
||||||
|
{ |
printf( |
|
"\n Ошибка |
75. |
Индексы |
вершин |
д.б. |
в " |
|||||||
|
|
|
||||||||||||||
|
|
exi |
t |
( 75 |
"диапазоне |
|
О. . %d |
\ л " , |
Gr.NumTop~l |
) ; |
||||||
|
|
) / |
|
|
|
|
|
|
|
|
|
|
|
|||
}
}
±£( RetCode < 3*Gr.NumArc )
{ |
|
|
|
|
|
Ошибка |
80. |
Ошибка |
чтения |
элементов |
" |
||||
|
printf( |
|
"\n |
|
|||||||||||
|
|
|
"массива |
ребер |
\п" |
) ; |
|
|
|
|
|
||||
|
exit |
( |
80 |
) |
; |
|
|
|
|
|
|
|
|
|
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Чтение |
информации |
о |
вершинах |
- |
старте |
и финише |
пути |
|||||||
RetCode |
= |
fscanf |
|
( |
pStrlnp, |
" |
%d", |
&start |
) ; |
|
|
||||
±£( |
RetCode |
/= |
1 |
) |
|
|
|
|
|
|
|
|
|
||
{ |
|
|
|
|
|
Ошибка |
90. |
Ошибка |
при |
чтении |
начальной" |
||||
|
printf( |
|
"\n |
|
|||||||||||
|
exit |
( |
" |
вершины |
пути |
\п" |
) ; |
|
|
|
|
|
|||
|
90 |
) |
; |
|
|
|
|
|
|
|
|
|
|
||
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
RetCode |
= |
fscanf |
|
( |
pStrlnp, |
" |
%d", |
& finish |
) ; |
|
|
||||
±£( |
RetCode |
!= |
1 |
) |
|
|
|
|
|
|
|
|
|
||
( |
printf( |
|
"\n |
|
Ошибка |
100. |
Ошмбка |
при |
чтении |
конечной" |
|||||
|
|
|
|||||||||||||
|
|
|
" вершины пути \п" ) ; |
|
|
|
|
|
|||||||
|
exit |
( |
100 |
) ; |
|
|
|
|
|
|
|
|
|
|
|
}
//Закрытие файла ввода
RetCodel |
= |
fclose( |
pStrlnp |
) ; |
||
±f( RetCodel |
== EOF ) |
|
|
|||
{ |
|
"\n |
Ошибка |
110. |
Ошибка закрытия файла %s \п", |
|
printf( |
|
|||||
|
|
pFilelnp |
) |
; |
|
|
exit |
( 110 ) |
; |
|
|
|
|
}
xretuxm/
276
// Печать данных о графе |
|
|
|
||
void. WriteGraph ( |
|
|
|
|
|
char |
*pFileOut,// |
Указатель на файл результатов |
|||
char |
*pMode ) |
// |
Указатель на режим открытия файла |
||
{ |
|
|
|
|
|
FILE |
*pStrOut/ // |
Указатель на структуру со |
|||
Int |
i, |
|
// |
сведениями о файле результатов |
|
// Индекс элемента массива |
ребер |
||||
|
RetCodel; |
// |
Возвращаемое значение |
fclose( ) |
|
//Открытие файла вывода
pStrOut |
= fopen( pFileOut, pMode ); |
|
±f( pStrOut |
== NULL ) |
|
{ |
|
"\n Ошибка 120, Файл %s для вывода не " |
printf( |
||
|
|
"открыт \л", pFlleOut ); |
exit |
( 120 ) ; |
|
}
//Печать информации о графе
|
fprlntf |
( pStrOutг |
"\п |
Число вершин графа: %d," |
|
|
" |
число ребер: |
%d \п"г Gr.NumTop, Gr.NumArc ) ; |
||
|
fprlntf |
( pStrOutr |
|
|
|
" \j^* |
* * * * -^ * * * * * * * * * |
-^ * * * * * * * * * * * * * * * * * * "^ * * * "^^ * * * * * * * * * * * * * |
|||
"\n |
Индекс ребра |
1-я вершина |
2-я вершина Вес ребра" |
||
"\п********************^**************************^*********"
"\п" ) ; |
|
|
|
|
tori 1 = о; |
1 < Gr.NumArc/ i + -i- ) |
|||
{ |
pStrOut, |
"%10d %14d %14d %17f \л", i, |
||
fprlntf( |
||||
|
Gr.pArcf |
1 |
].first, |
Gr.pArc[ 1 ],lastr |
|
Gr.pArcf |
i |
].weight |
); |
}
//Закрытие файла вывода
RetCodel |
= fclose( pStrOut ); |
|
±f( RetCodel -= EOF ) |
||
{ |
|
|
printf( |
"\n Ошибка 150. Файл %s не закрыт \n ", |
|
|
|
pFileOut ); |
exit |
( |
150 ); |
}
return;
}
Файл GrAlocFree. cpp. Размеш,ение массива с информацией о ребрах графа в динамической памяти и освобождение динамиче ской памяти, занятой этим массивом.
Используется в программном проекте для решения транспорт ной задачи.
277
_V |
Давыдов |
В.Г. |
|
Консольное |
|
приложение^ |
Visual |
C++ 6 |
|
j |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
/ / |
Включаемый |
файл |
программного |
проекта |
для |
решения |
|
|
||||||||||||||
// |
транспортной |
|
задачи |
|
(задачи |
|
|
коммивояжера) |
|
|
|
|
||||||||||
#include |
|
"GrHead.h" |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
// |
Размещение |
массива |
с |
информацией |
о |
ребрах |
графа |
в |
|
|
||||||||||||
// |
динамичнеской |
void |
памяти |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
void. GrAllocDM( |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
{ |
// |
Gr.NumTop |
- |
число |
вершин |
графа |
(определяется |
на |
|
|||||||||||||
|
|
|||||||||||||||||||||
|
// |
Gr. NumArc |
- |
внешнем |
|
уровне) |
|
(определяется |
на |
внешнем |
||||||||||||
|
// |
число |
|
ребер |
графа |
|||||||||||||||||
|
// |
Gr.pArc |
|
|
|
уровне) |
на |
начало |
массива |
с |
информацией |
о |
||||||||||
|
// |
- указатель |
|
|||||||||||||||||||
|
// |
|
|
|
ребрах^ |
|
размещенного |
в |
динамической |
|
памяти |
|
||||||||||
|
// |
pMinWay |
- |
(определяется |
|
на |
|
внешнем |
уровне) |
|
|
о |
||||||||||
|
// |
указатель |
|
на |
начало |
массива |
с |
информацией |
||||||||||||||
|
// |
|
|
|
наилучшем |
пути, |
размещенного |
в |
|
динамической |
||||||||||||
|
// |
|
|
|
памяти |
|
(определяется |
на |
внешнем |
уровне) |
|
|||||||||||
|
// |
Контроль |
корректности |
|
количества |
|
вершин |
|
графа |
|
|
|||||||||||
|
i£( |
Gr.NumTop |
|
< 2 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
{ |
printf( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"\п |
|
|
|
10. |
Число |
вершин |
графа |
должно быть |
более" |
|||||||||||||
Предупреждение |
|
|||||||||||||||||||||
" |
одной |
вершины" |
вершин, |
равное |
|
%d) . |
Принимается |
число" |
|
|||||||||||||
"\п |
(задано |
число |
|
|
|
|||||||||||||||||
" вершин, равное |
|
2." |
|
продолжается |
", |
Gr.NumTop |
) ; |
|
|
|||||||||||||
"\п |
Выполнение |
программы |
|
|
|
|||||||||||||||||
|
|
Gr.NumTop |
|
= |
2; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Контроль |
|
корректности |
|
количества |
|
ребер |
графа |
|
|
|||||||||||
|
if( |
Gr. NumArc |
< |
1 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
{ |
printf( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"\n |
|
|
|
20. |
Число |
ребер |
|
графа |
должно |
быть |
не" |
|
||||||||||
Предупреждение |
|
|
|
|||||||||||||||||||
" менее |
одного |
|
ребра" |
|
равное |
%d) . Принимается |
|
число" |
|
|||||||||||||
"\п |
(задано |
число |
ребер, |
|
|
|
||||||||||||||||
" ребер, |
равное |
|
1. |
" |
1; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Gr.NumArc |
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
} |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// |
Размещение |
массива |
ребер |
в |
динамической |
|
памяти |
|
|
||||||||||||
|
Gr.pArc |
= new А[ |
Gr. NumArc |
] ; |
|
|
|
|
|
|
|
|
|
|
||||||||
|
if( |
Gr.pArc |
|
== |
NULL |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
{ |
printf( |
|
"\n |
Ошибка |
30. Массив |
ребер |
в |
|
динамической" |
|
|||||||||||
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
" |
памяти |
не |
размещен |
" ) ; |
|
|
|
|
|
|
|||||||
|
|
exit |
( |
30 |
) |
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
}
11^
//Размещение массива структур с информацией о наилучшем
//пути в динамической памяти
pMlnWay = new W[ Gr. NumTop ] ; ±f( pMinWay == NULL )
|
{ |
|
|
|
printf( |
|
|
"\n |
Ошибка 40. |
Массив структур с информацией о наилучшем" |
|
" пути в \п" |
|
|
|
"\п |
динамической |
памяти не размещен " ) ; |
|
|
exit ( |
4 0 |
) ; |
}
// Инициализация массивов, размещенных в динамической
//памяти, нулевыми значениями
for( Int 1 = О; 1 < Gr.NumArc; i++ )
{ |
i J.firSt |
|
|
|
|
|
Gr.pArcf |
= 0; |
Gr.pArcf |
i |
],last |
= 0; |
|
Gr.pArc[ |
1 ].weight |
= O.Of; |
|
|
|
|
} |
|
|
|
|
|
|
£or( 1 = 0; 1 < Gr. NumTop/ 1 + + ) |
|
|
|
|||
{ |
|
|
|
|
|
|
pMlnWayf |
1 ]. exist |
= 0; |
pMinWayf |
i |
].ref |
= 0/ |
pMinWay[ i ] . SumDist = |
0.0; |
|
|
|
||
}
return;
}
// Освобождение динамическом памяти, занятой массивами ребер
//и структур с информацией о наилучшем пути
void. GrFreeDM( void )
{ |
|
|
|
|
|
i£( |
Gr.pArc |
/= NULL ) |
|
|
|
{ |
|
|
|
|
|
|
delete |
[ ] Gr.pArc; |
Gr.pArc = NULL; |
|
|
} |
|
|
|
|
|
if( |
pMinWay != NULL ) |
|
|
||
{ |
|
|
|
|
|
|
delete |
[ ] pMinWay; pMinWay = NULL; |
|
||
} |
|
|
|
|
|
return; |
|
|
|
|
|
} |
|
|
|
|
|
Файл Graph. cpp. |
|
|
|
||
Функции решения |
транспортной задачи: |
|
|||
* шаг вперед из |
достигнутой |
вершины по заданному ребру; |
|
||
* прохождение пути от достигнутой вершины InterMediate, |
если |
||||
он есть, |
до вершины |
finish; |
|
|
|
* поиск |
пути минимального веса в неориентированном взвешенном |
||||
279