Графы, алгоритм посещения всех ребер в обе стороны
255
12 февраля 2019, 12:50
Никак не могу придумать адекватный алгоритм выполнения задачи, гуглил перегуглил не нашел ничего подходящего, разве что Эйлеров путь, но это немножко не то.
Суть задачи: Нужно найти такой кратчайший маршрут по графу, что бы он проходил по всем ребрам, в оба направления, сам граф задается списком ребер ( матрицей смежности тоже вариант)
Подскажите алгоритм работы
Answer 1
Эйлеров путь как раз то. Он проходит по всем рёбрам по одному разу, т.е. короче сделать нельзя.
Надо только модифицировать граф - разделить каждое ребро на две противоположно направленных дуги.
A - B A => B
| <=
| ^ |
C | v
С
А дальше - алгоритм Хирхольцера, например. В трёх словах его описание
-
12:23
-
20:41
-
06:31
-
21:28
-
22:18
-
08:00
-
13:46
-
10:14
-
18:32
Сборка персонального компьютера от Artline: умный выбор для современных пользователей
ТОП-10
- Почему SERVER_ADDR имеет не тот IP 49918 visits
- Как заменить $_SERVER[REMOTE_ADDR] на IP клиента в PHP за двумя Nginx? 31901 visits
- Хочу вывести несколько строк из массива в один div, выводит только много undefined; подскажите, что делать? 25880 visits
- Как через css изменить цвет png изображения? 11723 visits
- Blob video url download 11268 visits
- Php curl запрос через прокси с авторизацией 10669 visits
- Работа с captcha vk api 9471 visits
© "hostciti.net" 23.12.2025 | 18:44