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

а) pебpам

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

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

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

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

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

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

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

М

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

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


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

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