| Вопрос: Графы | Добавлено: 22.05.04 18:50 |
Автор вопроса:  Alex_Spb
|
|
Нахождение кратчайшего пути в графе-дереве. Граф задан XML-файлом .Помогите, пожалуйста , написать эту прогу. |
| Ответы | Всего ответов: 2 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 23.05.04 00:08 |
|
Бектрекинг.
Создаешь массив ребер, пока не конечная точка, перемещаешься из текущей вершины в любую соседнюю, ребро до которой пройдено меньше 2 раз. Увеличиваешь в этом массиве число прохождений этого ребра. Кратчайший путь - последовательность ребер, помеченная 1.
Волновой алгоритм (алгоритм Ли)
Помечаешь все соседние вершины с твоей числом 1, перебираешь все соседние непомеченные с вершинами, помеченными n, и помечаешь их n+1, пока не добираешься до конечной точки. Кратчайший путь - последовательность, идущая от N (число в конечной точке) до 1 сверху вниз.
|
||
|
Номер ответа: 2 Автор ответа:  Alex_Spb Вопросов: 2 Ответов: 1 |
Профиль | | #2 | Добавлено: 23.05.04 11:36 |
|
Благодарю . Попытаюсь написать код |
||
Страница: 1 |