VPF::работа с графами - Форум программистов

Себастьян

Дата 5.6.2005, 18:27 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 1.6.2005

Репутация: нет
Всего: нет

Блин я уже так задолбался с этим заданием, а скоро нужно
уже сдавать
может кто нибудь поможет:
Построить алгоритм поиска кратчайшего пути
между двумя вершинами в графе. Связывать можно
только четные с нечетными вершинами.
Или хотя бы дайте какие нибудь методички по
графам

dvs

Дата 6.6.2005, 19:43 (ссылка)

(нет голосов)

Загрузка ...

Владимир Драпалюк

Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19

Классика жанра...
http://forum.vingrad.ru/index.php?showtopic=54334
Там есть кучка хороших ссылок...

В принципе можно использовать алгоритм Дейкстры, просто тебе для начала необходимо составить граф, точнее его матрицу смежности, удолетворяющую условию задачи (соединены четные с нечетными)
Или пользуйся самым простым "Волновым алгоритмом"

Цитата

Волновой алгоритм
Дано: невзвешенный граф G=(V,E). Требуется найти путь между вершинами s и t графа, содержащий минимальное количество промежуточных вершин.
1. каждой вершине vi приписывается целое число T(vi) - волновая метка (начальное значение T(vi)=-1);
2. заводятся два списка OldFront и NewFront (старый и новый "фронт волны"), а также переменная T (текущее время);
3. OldFront:={s}; NewFront:={}; T(s):=0; T:=0;
4. для каждой из вершин, входящих в OldFront, просматриваются инцидентные (смежные) ей вершины uj, и если T(uj) = -1, то T(uj):=T+1, NewFront:=NewFront + {uj};
5. если NewFront = {}, то ВЫХОД (нет решения);
6. если tNewFront (т.е. одна из вершин uj совпадает t), то найден кратчайший путь между s и t с T(t)=T+1 промежуточными ребрами; ВЫХОД (решение найдено);
7. OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4).
Замечание
На шаге (4) "соседними" вершинами для неориентированных графов считаются все смежные вершины, а для орграфов - вершины, в которые из данной вершины ведут дуги.
Если на шаге (6) была достигнута вершина t, то восстановить кратчайший путь можно следующим образом: среди соседей вершины t найдем любую вершину с волновой меткой T(t)-1, среди соседей последней - вершину с меткой T(t)-2, и т.д., пока не достигнем s. Найденная последовательность вершин определяет один из кратчайших путей из s в t. На практике выгодно сохранять на шаге (4) информацию о том, из какой вершины "волна" пришла в вершину uj - тогда восстановление пути осуществляется быстрее.

Цитата

Алгоритм Дейкстры
Наиболее эффективный алгоритм для неотрицательных весов дал Дейкстра. Этот алгоритм основан на том, что каждому узлу приписывается расстояние Dist до s и признак возможности изменять это расстояние Visit, которые меняются в процессе работы алгоритма. Алгоритм, предложенный Дейкстром, предназначен для определения кратчайшего пути между вершинами s и t, если все веса графа неотрицательны Aij0. Алгоритм основан на итерационном уточнении значений элементов массива Dist[xi], которые в начальный момент времени содержат большие величины, а в конце выполнения алгоритма уменьшаются и содержат длину кратчайшего пути от s к вершине xi. Основная идея уточнения основана на простой формуле Dist(xi)=Min(Dist(xi), Dist(p)+Api).

Если между вершинами p и xi нет ребра, то Api =MaxInt и Dist(xi) не меняется. Если же между этими вершинами есть ребро и Dist(p) уже достигло минимального значения, то Dist(xi) также принимает минимальное значение.
В начале работы алгоритма выделен только узел s, в процессе – выделены некоторые узлы, в конце - все. При этом:
 для каждого выделенного узла i в Dist хранится наименьшая стоимость пути si;
 известно, что минимум достигается на пути, проходящем только через выделенные узлы;
 для каждого невыделенного узла i хранится наименьшая стоимость пути si, в котором в качестве промежуточных используются только выделенные узлы.
Множество выделенных узлов расширяется на основании следующего замечания: если среди всех невыделенных узлов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный узел на этом пути - уже до него путь длиннее! Здесь существенна неотрицательность цен.
Добавив выбранный узел к выделенным, мы должны скорректировать информацию, хранимую для невыделенных узлов. При этом достаточно учесть лишь ребра, в которых новая вершина является последней, а это легко сделать, так как минимальную длину пути в новый узел мы уже знаем.
Если для хранения множества выделенных узлов задан массив логического типа, то добавление одного узла к числу выделенных требует времени O(n).
В процессе работы алгоритма Dist[xi] переходят из состояния «можно изменять» в состояние «менять нельзя». Вначале только у элемента Dist[s], имеющего значение 0, ставится пометка «менять нельзя» Visit=true и на каждом шаге итерационного процесса такая пометка ставится еще у одного элемента. Процесс заканчивается, когда у всех элементов ставится пометка «менять нельзя», т.е. за N-1 шагов.
Для реализации этого алгоритма уточним структуру, описывающую узлы:
Листинг
 TNode=record
 Name : string; // имя узла
 Edge : array of TEdge; // массив дуг
 Visit : boolean; // были
 x0,y0 : integer; // центр
 NumVisit: integer; // № посещения
 Color : TColor;
 Dist : integer;//минимальное расстояние до s
 end;
В записи TNode появилось поле Dist, предназначенное для хранения расстояния до узла s.
Алгоритм Дейкстры (Aij0)
Шаг 1. Присвоение начальных значений. Положить Dist(s)=0 и считать этот узел помеченным Visit(s)=true, т.е. в дальнейшем Dist(s) не изменяется. Положить Dist(xi)= . Положить p=s.
Шаг 2. Обновление Dist. Для всех непомеченных узлов xiГ(p) уточнить Dist по формуле Dist(xi)=Min(Dist(xi), Dist(p)+Api).
Шаг 3. Отметить один узел. Среди всех непомеченных узлов найти такой, для которого Dist(xi*)=Min(Dist(xi)) и пометить его.
Шаг 4. Положить p=x*.
Шаг 5. Если p=s, то ОСТАНОВ иначе перейти к шагу 2.
В листинге 14.25 приведена нерекурсивная функция, реализующая этот алгоритм.
Листинг 14.25.
 function Dijkst(s,t: integer): integer;
 // алгоритм Дейкстры
 var i,p: integer;
 begin
 ClearVisit; SetMatr;
 // Шаг 1. Инициализация
 L:=Length(Node);
 for i:=0 to L-1 do
 with Node[i] do Dist:=MaxInt0;
 Node[s].Dist:=0; VisitTrue(s);
 p:=s;
 repeat
 p:=FindMinDist(p); // Шаги 2,3,4. Обновление Dist и найти Min
 VisitTrue(p); // пометка=false
 until p=t; // Шаг 5.
 Result:=Node[p].Dist;
 PathToStack(s,p);
 end;

Эта функция возвращает минимальное расстояние от узла s до узла t. Шаги 2 и 3 реализует функция FindMinDist(p).
Листинг 14.26. Уточнение Dist и определение Min
 function FindMinDist(p: integer): integer;
 var i,MinDist: integer; Ok: boolean;
 begin
 MinDist:=MaxInt0;
 for i:=0 to L-1 do // цикл по всем узлам
 with Node[i] do
 if not Visit then begin // смотрим не помеченные узлы
 Dist:=Min(Dist,Node[p].Dist+A[p,i]); // уточняем Dist
 if Dist<MinDist then begin // накапливаем Min
 MinDist:=Dist; Result:=i;
 end;
 end;
 end;
Алгоритм Дейкстры не определяет минимальный путь, т.е. последовательность вершин, по которым надо пройти от s до t. Но этот путь можно получить с помощью рекурсивного соотношения Dist(xi*)+A(xi*,xi)=Dist(xi), т.к. вершина xi* предшествует вершине xi на минимальном пути. Эту рекурсию реализует процедура PathToStack(s,p), которая помещает вершины минимального пути в стек:
Листинг 14.27.
 procedure PathToStack(s,p: integer);
 var i: integer; Ok: boolean;
 begin
 Stack_Init(Stack); // инициализировать стек
 while p<>s do begin
 Push(Stack,p); // поместить в стек
 i:=-1; Ok:=false;
 while (i<L-1) and not Ok do begin
 Inc(i); Ok:=(i<>p) and (Node[p].Dist=Node[i].Dist+A[i,p]);
 end;
 p:=i;
 end;
 end;
Замечание
Для определения минимального расстояния от вершины s до всех вершин графа в функции необходимо заменить цикл repeat на цикл for i:=1 to N-1 do, т.к. на каждом шаге алгоритма помечается ровно одна вершина, а перед началом работы одна вершина уже помечена.

--------------------

Любите друг друга!

Себастьян

Дата 6.6.2005, 19:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 1.6.2005

Репутация: нет
Всего: нет

только мне надо не на Pascal а на C++

dvs

Дата 6.6.2005, 19:57 (ссылка)

(нет голосов)

Загрузка ...

Владимир Драпалюк

Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19

http://algolist.manual.ru/maths/graphs/sho...th/dijkstra.php
Внизу, а то вдруг не увидишь, в комментариях есть пример на С...

--------------------

Любите друг друга!

Себастьян

Дата 18.6.2005, 13:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 1.6.2005

Репутация: нет
Всего: нет

Блин ничего не получается

dvs

Дата 18.6.2005, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Владимир Драпалюк

Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19

Себастьян, давай по порядку - что не получается?
1. Ты понимаешь механизм работы алгоритма на уровне блоксхемы? Нужно еще несколько раз прочитать статью по ссылке выше и порисовать на бумаге. Вообщем-то, это нужно делать до получения результата.
2. У тебя проблемы с реализацией? Тогда показывай свой код и рассказывай, в каком месте не работает.
3. Тебя ломает что-либо делать? Тогда забей, всех ломает. Подсказать - это одно, а выполнить всю работу - это другое. Надеюсь ты, как здравомыслящий человек, эту разницу понимаешь.

--------------------

Любите друг друга!

Себастьян

Дата 19.6.2005, 09:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 1.6.2005

Репутация: нет
Всего: нет

Вообщем чего то тут я написал,но не работает, не знаю в чём ошибка
Обозначения:

C[i,j]- длина ребра(i,j), С[i,j]>=0 (если ребра нет, то его длина полагается
равной бесконечности).

D[i]- кратчайшее текущее расстояние от вершины нач до вершины i.

fl[i]- информация о просмотре вершины i: 0 - если вершина не просмотрена,
1 - если просмотрена. Если вершина просмотрена, то для нее
D[i] есть наикратчайшее расстояние от вершины нач до вершины i.

pr[i]- информация о номере вершины, предшествующей вершине i
в кратчайшем пути от вершины нач.

min - это минимальное расстояние.

Код


#include<iostream.h>
#include<conio.h>
#include<bios.h>
#include<math.h>
main()
{
clrscr();
int n,ver,k,j,min;
cout<<"\n Vvedite kolichestvo vershin v graphe \n";
cin>>n;
for(int i=1;i<n;i++)
pr[i]=ver;         {пока мы знаем только расстояние}
fl[i]=0;             {от вершины нач до нее же, равное 0}
d[i]=c[ver,i];
fl[ver]=1;
pr[ver]=0;
for(i=1;i<n-1;i++)
min>=0;
for(j=1;j<n;j++)
if((fl[j]=0) && (min>d[j]))  {находим минимальное}
min=d[j];    {расстояние}
k=j;           {до непомеченных вершин}
fl[k]=1;     {вершина k помечается просмотренной}
for(j=1;j<n;j++)
if((fl[j]=0) && (d[j]>d[k]+c[k,j])){Т.е. если для вершины j еще не найдено кратчайшее расстояние 
от нач, и из вершины k по дуге C[k,j] путь в j короче, 
чем найденный ранее}

d[j]=d[k]+c[k,j];{то запоминаем его}
pr[j]=k;
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »