Задача на графы

Guf96rUS

Что-то не могу сообразить, как решить такую задачу:
Дан связный граф с ребрами единичной длины. В графе две вершины помечены как А и В. Требуется найти такую минимальную длину пути из А в В, которая удовлетворяет требованию ее четности либо нечетности.
Например:
Задан граф с вершинами А, В, С.
Граф содержит ребра АВ, АС, СВ.
Нужно найти минимальную четную длину пути из А в В.
Ответ: 2 (АС, СВ)
Нужно найти минимальную нечетную длину пути из А в В.
Ответ: 1 (АВ)

Guf96rUS

Разрешается использовать алгоритм сложности не выше n^4 по количеству вершин

Guf96rUS

Путь может содержать одинаковые вершины и ребра
Требуется уметь распознавать ситуации, при которых построение пути с длиной заданной четности невозможно

Xephon

обход в глубину (он же - волновой алгоритм) до уровня 2*n
если в слоях нужной четности не было вершины B - значит ее не будет никогда

the_witcher666

Обход в глубину экспоненциален

Xephon


Во даете!
Каждый раз хранится слой достижимых за n ходов вершин.
Слой n+1 получается как соседние вершины к n-ому слою.
Не больше чем 2*V шагов: обработка каждый раз не более чем V вершин графа * E ребер
Итого сложность V^2*E

Guf96rUS

Вообще-то то, о чем ты говоришь - это обход в ширину, а не в глубину. Но вообще - спасибо

Xephon

А, ну да , черт попутал.
Вообще, думаю, есть и меньшей сложности.
Лень думать

Xephon

Хотя, недолго думав... Вот еще вот алгоритм; сложность не выше V^3, точнее можешь оценить сам - для тех графов, которые тебе нужны
0) Ищешь кратчайший путь алгоритмом Дейкстры, если он - нужной тебе четности, то все шоколадно.
Если не нашел:
1) Для поиска кратчайшего четного пути:
Из графа G строим "граф четных путей" G'. Он устроен так: вершины A и B соединены в G', если есть такая вершина C, что AC, BC - ребра в G. (Очевидно как написать такой алгоритм сложности v^3).
Потом в новом графе ищешь кратчайший путь алгоритмом Дейкстры.
2) Для поиска кратчайшего нечетного пути:
Делаешь граф Q из G таким образом: создаешь новую вершину T, которая имеет только одну соседнюю - A. Для этого графа применяешь алгоритм из п.2 поиска кратчайшего четного пути из вершины T в вершину B

kiritsev

ну например тривиальное решение:
расщепляем каждую вершину на две v -> v1, v2
если есть ребро v-u то есть рёбра v1-u2 и v2-u1
а дальше находим кротчайший путь от a1 до b1 или b2 в зависимости что нужно.

Xephon

Ага. Муд(р)ить оказалось не нужно

kiritsev

угу, обожаю графовые задачи.
:
откуда эта, или куда?

Nonnik

Кажись так прикольней:
  
///////////Input://///////////////////////////////
G=(V,E) Graph;
///////////////initialization://///////////////////
D_even[A,A] = infinity;
D_odd[A,A] = 0;
for_each(vertex V): D_even[A,V] = infinity; D_odd[A,V] = infinity;
///////////////////////body:///////////////////////////
D_even[A,B] = min_{for all inedges (U,B)}[D_odd[A,U] + weight(U,B)];
D_odd[A,B] = min_{for all inedges (U,B)}[D_even[A,U] + weight(U,B)];
Оставить комментарий
Имя или ник:
Комментарий: