Задача на графы - Форум «Всё о Паскале»

Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++

Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

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

Опции

Marisha1	17.05.2009 18:06 Сообщение #1
Группа: Пользователи Сообщений: 3 Пол: Женский Репутация: 0	Здравствуйте. Помогите решить задачу: Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по а) pебpам б) веpшинам. Заранее спасибо!

Ответов

passat	19.05.2009 16:00 Сообщение #2
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0	Цитата(Marisha1 @ 17.05.2009 14:06) Здравствуйте. Помогите решить задачу: Найти кратчайшее расстояние между двумя вершинами в графе. Кратчайшее в каком смысле? Если по количеству ребер - поиск (если склероз не изменяет, в ширину). Если по стоимости - Дейкстра. Цитата Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по а) pебpам б) веpшинам. Заранее спасибо! Первая задача простая - упрощенный максимальный поток: всем ребрам задаем единичную пропускную способность и находим максимальный поток. После нахождения его, треклятого, поток будет течь только по искомым ребрам. Вторая посложнее. Надо разбить каждую вершину, кроме истока и стока, на две и соединить ребром. Таким образом задача сводится к предыдущей. В конце просто посчитать дуги, выходящие из истока. ПС. Это где это все три задачи предлагают вместе?