Версия для печати темы

Автор: Marisha1 17.05.2009 18:06

Здравствуйте. Помогите решить задачу:
Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по

а) pебpам

б) веpшинам.
Заранее спасибо!

Автор: Lapp 18.05.2009 4:54

Marisha1, ты не ошиблась разделом? Тебе нужно чисто математически решить эту задачу в общем виде для всех графов? Я - пас..

Или тебе все-таки надо программу сделать?

Автор: Marisha1 18.05.2009 14:09

Необходимо программу сделать. Подскажите хоть в чем?

Автор: Lapp 18.05.2009 14:32

Что значит "в чем"? В смысле, на каком языке?.. Это ты должна сказать, думаю.

Автор: Marisha1 18.05.2009 23:57

Pascal или Delphi. Может алгоритм есть нахождения путей?

Автор: Lapp 19.05.2009 0:31

Есть один алгоритм - "полный перебор" называется))..
Начинай делать. Поможем.

М

Тему наконец переношу в раздел Задачи

Автор: passat 19.05.2009 16:00

Кратчайшее в каком смысле? Если по количеству ребер - поиск (если склероз не изменяет, в ширину). Если по стоимости - Дейкстра.


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

ПС. Это где это все три задачи предлагают вместе?