Задан граф, имеются 2 вершины : исходная и конечная...Необходимо найти наибольшую пропускную способность графа.... P.S.как я понял кол-во вершин задается юзером, ребра м/у вершинами являются пропускной способностью...Например [а,б]=с; где а,б-вершины, с-пропускная способность м/у ними....
Вот мой вариант, только тут есть маленький партак.....Он выводит общее кол-во путей...А необходимо наибольший поток данных...
uses wincrt; var map:array [1..30,1..30] of integer;{Карта: map[i,j] не 0, если точки i и j соединены} road:array [1..30] of integer;{маршрут-номера точек карты} road1:array [1..30] of integer; incl:array [1..30] of boolean;{incl[i]=true, если точка с номером i включена в road} len:integer; {Длина последнего найденного маршрута} c_len:integer; {длина текущего маршрута} start,finish:integer;{Начальная и конечная точки} i,j:integer; n:integer; {Кол-во вершин в графе} potok:integer; {Пропускная способность} w,z,max:integer; procedure init; begin writeln('Введите кол-во вершин в графе-> '); readln(n); for i:=1 to N do road[i]:=0; for i:=1 to N do incl[i]:=false; for i:=1 to n do for j:=1 to n do map [i,j]:=0; end;
procedure creat; begin w:=0; while w<>2 do begin writeln('1-добавление связи м/у 2-мя вершинами'); writeln('2-выход'); readln(w); case w of 1:begin write('Введите ч/з пробел номера вершин-> '); readln(i,j); writeln('Введите пропускную способность м/у ними-> '); readln(potok); map[i,j]:=potok; end; end; end; end;
procedure step(s,f,p:integer); var c:integer; {номер точки в которую делаем очередной шаг} begin if s=f then begin len:=c_len; {сохраняем длинну найденного маршрута} write('путь: '); for i:=1 to p-1 do write(road[i],' '); writeln (' Пропускная способность: ',len); end else {выбираем очередную точку} for c:=1 to n do {проверяем все вершины} if (map[s,c]<>0) and (not incl[c]) {and ((len=0) or (c_len+map[s,c]>len)) } {точка соединена с текущей и не включена в маршрут} then begin road[p]:=c; {добавим вершину в путь} incl[c]:=true; {пометим вершину, как включенную} if c_len=0 then c_len:=map[s,c]; if c_len>map[s,c] then c_len:=map[s,c];
{procedure maximum; begin for i:=1 to n do begin writeln('Максимальный поток данных проходит ч/з '); writeln('Путь ',road[i+1]); writeln('Пропускная способность ',max); end; end;}
procedure run_map; begin init; creat; write ('Введите через пробел номера начальной и конечной точек -> '); readln (start,finish); road [1]:=start; {Внесем точку в маршрут} incl [start]:=true;{пометим ее как включенную} len:=0; c_len:=0; step (start,finish,2); {ищем вторую точку} {maximum;} writeln ('Для завершения нажмите <Enter>'); readln; end;
Алгоритм Форда в чистом виде, был такой на лекции? Там нужно находить произвольный путь, вычитать пропускную способность минимального ребра из этого пути, а промежуточный результат увеличить на это число и искать другой путь и т.д. пока граф не "распадётся". Скажем дружно- нафиг нужно!
на лекции не было.....Взял из книжки..Там пример нахождения мин.дороги....(процедура step) Путь не произвольный....Он задается юзером(кол-вом вершин)....я вот тут и завис .....на данном этапе выводит все возможные пути и их пропускную способность......макс путь чет ненаю... ПросТИте За коРявЫй ПочЕрКК...
не-не-не.... не так тут. пусть на входе имеем такой граф: Х 7 8 0 7 Х 3 1 8 3 Х 2 0 1 2 Х Графически это выглядит так:
найдём пропускную способность из 1 в 3. Случайным образом выбираем маршрут, например 1-2-3, 2-3 имеет минимальную пропускную способность, мы её запоминаем и вычитаем из всех веток маршрута, получаем такой граф:
Снова выбираем случайный маршрут, например 1-3, его пропускная способность 8, вычитаем её из всего маршрута и прибавляем к общей(до этого момента там была тройка). Теперь граф такой:
Опять ищем путь. Находим 1-2-4-3, минимальная пропускная способность равна единице 2-4. Добавляем единицу к общей пропускной способности, она уже равна 3+8+1=12 и вычитаем из всех веток маршрута. Граф теперь такой:
Больше путей нет, поэтому 12- это окончательный ответ.
Не, не..Я вот как говорил так оно и есть.....Сеня с преподом говорил.... Тот код,который я выше выложил полностью рабочий... Мне его как говорится удтвердили.......Только есть одно но,надо условие добавить чтобы он не все возможные пути выдавал, а один с максимальной пропускной способностью....
Quote
Случайным образом выбираем маршрут
маршрут задает юзер......... И еще пропускные способности не складываются!!!На всем маршруте находится мин пропускная способность....она и будет пропускной способностью всего заданного маршрута.....
Добавлено (25.11.2008, 18:20) --------------------------------------------- де тута файл моно прикрепить??Невижу....
ПросТИте За коРявЫй ПочЕрКК...
Сообщение отредактировал M@D - Среда, 26.11.2008, 01:11
procedure scan_graf; {ПРоцедура проверки правельности введенного графа} var p,g,q:integer; a,s,d:boolean; begin
q:=0; for i:=1 to n do begin p:=0; for j:=1 to n do
if map[i,j]<>0 then inc(p); if p=0 then inc(q); end; if q=1 then begin q:=0; for i:=1 to n do begin p:=0; for j:=1 to n do
if map[i,j]<>0 then inc(p); if p=0 then inc(q); end; end; if q=1 then {begin writeln('Является');}a:=true {end } else a:=false; if a<>true then begin writeln('Ошибка при вводе данный. Программа завершает работу!'); HAlt; end; end;
procedure step(s,f,p:integer);{нахождение максимальной пропускной способности} var c:integer; {номер точки в которую делаем очередной шаг} begin
if s=f then begin
len:=c_len; {сохраняем длинну найденного маршрута} if max<len then max:=len;
for i:=1 to p-1 do begin k:=0; if max=len then begin inc(k); road1[i]:=road[i]; inc(schet); end; end; { writeln (' Пропускная способность: ',len);} c_len:=0; end else {выбираем очередную точку} for c:=1 to n do {проверяем все вершины} if (map[s,c]<>0) and (not incl[c]) {точка соединена с текущей и не включена в маршрут} then begin road[p]:=c; {добавим вершину в путь} incl[c]:=true; {пометим вершину, как включенную}
if c_len=0 then c_len:=map[s,c]; if c_len>map[s,c] then c_len:=map[s,c];
step(c,f,p+1); incl[c]:=false; road[p]:=0;
end; end;
Вот ....Я ее все таки осилил)) Осталось тока все в файл записать..И вкршины ьрать из файла.. Редактирование предусмотреть!!