Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++
Прочтите прежде чем задавать вопрос!1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
  |
| Задача на графы |
| Marisha1 |
Сообщение
#1
|
|
Группа: Пользователи Сообщений: 3 Пол: Женский Репутация:  0   |
Здравствуйте. Помогите решить задачу:
Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по а) pебpам б) веpшинам. Заранее спасибо! |
   |
 
|
| Lapp |
Сообщение
#2
|
 Уникум  Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Marisha1, ты не ошиблась разделом? Тебе нужно чисто математически решить эту задачу в общем виде для всех графов?
 Я - пас..Или тебе все-таки надо программу сделать? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|
|
|
| Marisha1 |
Сообщение
#3
|
|
Группа: Пользователи Сообщений: 3 Пол: Женский Репутация: 0 |
Необходимо программу сделать. Подскажите хоть в чем?
|
|
|
|
| Lapp |
Сообщение
#4
|
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Цитата(Marisha1 @ 18.05.2009 11:09)  Подскажите хоть в чем? Что значит "в чем"? В смысле, на каком языке?.. Это ты должна сказать, думаю.-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|
|
|
| Marisha1 |
Сообщение
#5
|
|
Группа: Пользователи Сообщений: 3 Пол: Женский Репутация: 0 |
Pascal или Delphi. Может алгоритм есть нахождения путей?
|
|
|
|
| Lapp |
Сообщение
#6
|
|||
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Цитата(Marisha1 @ 18.05.2009 20:57) Может алгоритм есть нахождения путей? Есть один алгоритм - "полный перебор" называется))..Начинай делать. Поможем.
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|||
|
|
|
|||
| passat |
Сообщение
#7
|
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
Цитата(Marisha1 @ 17.05.2009 14:06) Здравствуйте. Помогите решить задачу: Найти кратчайшее расстояние между двумя вершинами в графе. Кратчайшее в каком смысле? Если по количеству ребер - поиск (если склероз не изменяет, в ширину). Если по стоимости - Дейкстра. Цитата Найти все возможные пути между этими двумя вершинами в графе не пеpесекающиеся по а) pебpам б) веpшинам. Заранее спасибо! Первая задача простая - упрощенный максимальный поток: всем ребрам задаем единичную пропускную способность и находим максимальный поток. После нахождения его, треклятого, поток будет течь только по искомым ребрам. Вторая посложнее. Надо разбить каждую вершину, кроме истока и стока, на две и соединить ребром. Таким образом задача сводится к предыдущей. В конце просто посчитать дуги, выходящие из истока. ПС. Это где это все три задачи предлагают вместе? |
|
|
|
|
|
Текстовая версия | 27.04.2024 23:34 |
