Теория Графов

SasSani4
Дата: 06.12.2007 15:23:36
Здраствуйте, помогите пожалуста решить в паскале (или Делфе) такую задачу:
"Найти все вершины графа, к каким существует путь заданой длины от ввыделеной его вершины" и "Найти длину самого короткого цыкла в графе"
ПОЖАЛУСТА!!! заранее благодарен.
Dimitry Sibiryakov
Дата: 06.12.2007 15:34:24

SasSani4

"Найти все вершины графа, к каким существует путь заданой длины от
ввыделеной его вершины"

Метод Форда-Фалкерсона рулит.

Posted via ActualForum NNTP Server 1.4

Warstone
Дата: 06.12.2007 15:37:15
SasSani4
Здраствуйте, помогите пожалуста решить в паскале (или Делфе) такую задачу:
"Найти все вершины графа, к каким существует путь заданой длины от ввыделеной его вершины" и "Найти длину самого короткого цыкла в графе"
ПОЖАЛУСТА!!! заранее благодарен.

Хм... Метод Взрыва или Фронто-Волны (Ну низнаю как эти методы по Дяденькам называются) с пометкой тех, по которым уже прокатило...
SasSani4
Дата: 06.12.2007 15:41:56
Метод Форда-Фалкерсона рулит.

а можна хоть какой-то мало-мальский пример, а то вообще понития не имею что єто такое
Dimitry Sibiryakov
Дата: 06.12.2007 16:11:58

SasSani4

а можна хоть какой-то мало-мальский пример, а то вообще понития не имею
что ?то такое

Заводится массив весОв размером по числу вергин графа. Заданной вершине
дается вес 0, остальным - бесконечность. Далее бесконечный перебор дуг.
Если разница весов концов дуги больше длины дуги, вес начала уменьшается
до веса конца+длина дуги. И так пока алгоритм не сойдется.

Posted via ActualForum NNTP Server 1.4