Графы. Помогите с алгоритмом

[Gennadiusisus]

Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.

Заранее спасибо =)

[martinges]

Дано матрица смежности(только модернизировать надо так как движение одностороннее)

Динамическая структура или массив хранящий путь и промежуточный граф откуда постепенно будем удалять пройденные дороги

Маркер прохода через вершину С(булева)

_________________________________

Фиксируем вершину А

Перебираем все вершины куда сможем приехать из А, допустим это будет X(первая попавшаяся ) удаляем из массива или дин структуры дорогу(ребро графа), добавляем путь в массив, хранящий путь

Повторяем алгоритм для вершины X, если X это С, поднимаем маркер. Если X это B и маркер true то выводим на экран насколько мы крутые))

P.S. Не оптимально наверное, но результат даст

P.P.S При поиске можно создать рекурсивную процедурку или функцию, которой ты скармливаешь граф и внутри этой функции/процедуры ты будешь скармливать уже "похудевший" на одну дорогу граф Вот только при больших массивах данных тормозит зараза)

[Innk]

http://e-maxx.ru/algo/

вот если понимаешь найдёшь алгоритм, поменяешь маленько )

1)Сначала же нам нужно дойти до С, вопрос - можно ли идя до С пройти через В, и потом по другим дорогам вернутся в В ?

Или дошли до С, потом через А дошли до В

Если нет, то это вроде простой поиск в глубину(в ширину), до В, с хранением дополнительной метки, заходили ли мы в С - полный перебор )

2)какие ограничения на задачу - количество рёбер, вершин ?

3)И конечно в мире существует только один язык программирования ))

Где такие задачи задают ? И много ли ?

[martinges]

1)Предполагаю что в одну вершину могут вести как входящие в город так и выходящие из него) так что в каком то случае возможен вариант возвращения в города по нескольку раз

2) представляю облом если будет миллион вершин и изолированный город B, а бедная программулька все будет искать и искать))

3)assembler гг

Хорошие задачки)) мозги так и радуются))

[Gennadiusisus]

http://e-maxx.ru/algo/

вот если понимаешь найдёшь алгоритм, поменяешь маленько )

1)Сначала же нам нужно дойти до С, вопрос - можно ли идя до С пройти через В, и потом по другим дорогам вернутся в В ?

Или дошли до С, потом через А дошли до В

Если нет, то это вроде простой поиск в глубину(в ширину), до В, с хранением дополнительной метки, заходили ли мы в С - полный перебор )

2)какие ограничения на задачу - количество рёбер, вершин ?

3)И конечно в мире существует только один язык программирования ))

Где такие задачи задают ? И много ли ?

Каждую дорогу можно проехать один раз, то есть, если есть несколько путей из "А" в "С", то нужно выбрать тот, который не препятствовал бы дальнейшему переходу в "В"

Ограничений больше нету...вроде...=)

Пишу на С++

У первочей в техноложке курсачи такие...не удержался что бы не попробовать запрогать =)

Добавлено спустя 24 минуты 21 секунду:

1)Предполагаю что в одну вершину могут вести как входящие в город так и выходящие из него) так что в каком то случае возможен вариант возвращения в города по нескольку раз

2) представляю облом если будет миллион вершин и изолированный город B, а бедная программулька все будет искать и искать))

3)assembler гг

Хорошие задачки)) мозги так и радуются))

ассемблер зло, фу фу фу...=]

а задачка и правда интересная =) и готовых алгоритмов под нее нету (не нашел по крайней мере)

[Innk]

Пруд пруди таких задачек )

Вот здесь если решил, то точно узнаешь правильно или нет

http://acm.timus.ru/problemset.aspx

http://codeforces.ru/contests

http://acm.mipt.ru/

и куча других

Вот я нарешал ))

http://acm.timus.ru/author.aspx?id=105123 - это к олимпиадам готовлюсь.

от вуза по 3 человека в команде ездим на четверть/полу финал ACM ICPC

Если просто интересно то вот почитать можно

Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализ

http://e-maxx.ru/bookz/