|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mike Girkin 2:5055/177.22 03 Jun 2003 11:57:05
To : Eugene Paniukov
Subject : Re: ряд задач для взвешанного орграфа
--------------------------------------------------------------------------------
20 Май 03 23:03, Eugene Paniukov закинул письмецо для All:
EP> 1. Проверить взвешанный орграф на нецикличность
Взвешенность орграфа на его цикличность не влияет.
Точно не помню, лекции трехгодичной выдержки влом искать. Hо есть идеи:
1. Вершина, из которой не исходит ни одной дуги не входит в цикл - отбрасываем
ее, и все дуги ей инцидентные.
2. Вершина, в которую не входит ни одной дуги не входит в цикл, отбрасываем ее
и все дуги ей инцидентные.
Повторяем шаги 1,2 пока есть удаляемые вершины. Как только ни одной вершины
удалить нельзя заканчиваем, и смотрим, если вершины еще остались - циклы есть,
если вершин не осталось, циклов нет.
EP> 2. Hайти все пути (от сюда найти растояния вполне реально)
Поиск в глубину.
EP> 3. Макс(мин) путь от текущей вершины до указанной (конец или начало)
Минимальный путь - агоритм Дейкстры. Максимальный путь, тоже как ни странно он.
Только надо пересчитать веса дуг, ну например так: Rnew=Rmax-Rold. Где Rnew -
новый вес, Rold - старый вес, Rmax - максимальный вес в графе. И найти
минимальный путь.
Тьма за нас. Mike .
... Hе плюй в колодец - там же никого нет...
--- GoldED+/W32 1.1.5-030118
* Origin: (2:5055/177.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: ряд задач для взвешанного орграфа