Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 2 379

/ вопрос открыт /

Здравствуйте!Подскажите пожайлуста, как найти и вывести путь между заданными вершинами графа?

Milady Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задала: Milady (статус: Посетитель)
Вопрос отправлен: 2 февраля 2009, 18:11
Состояние вопроса: открыт, ответов: 0.


Мини-форум вопроса

Всего сообщений: 5; последнее сообщение — 2 февраля 2009, 19:15; участников в обсуждении: 3.
Вадим К

Вадим К (статус: Академик), 2 февраля 2009, 18:24 [#1]:

А как сам граф задан?
в общем, задача решается обычной банальной рекурсией. То есть, вначале запускается рекурсия с одной вершины, и когда достигается другая, то выписывается путь. Если надо найти путь легче (то есть есть цена веток), то надо составлять список возможных путей...
Задача решаема, главное иметь полное условие.
Галочка "подтверждения прочтения" - вселенское зло.
Milady

Milady (статус: Посетитель), 2 февраля 2009, 18:39 [#2]:

граф такой: 6 узлов и 7 ребрер,неориентированный, взвешенный, его матрица смежности:
0 5 0 0 0 7
5 0 4 0 0 0
0 4 0 2 1 0
0 0 2 0 3 0
0 0 1 3 0 8
7 0 0 0 8 0
а как программно реализовать поиск путей?
Вадим К

Вадим К (статус: Академик), 2 февраля 2009, 18:45 [#3]:

к сожалению, я не знаю, как читать такие матрицы смежности. Хотя есть идеи как... А так как я не знаю, как он выглядит.... я ничего не могу помочь
Галочка "подтверждения прочтения" - вселенское зло.
Dron

Dron (статус: Студент), 2 февраля 2009, 19:01 [#4]:

Обычно матрицы смежности задаются квадратными матрицами: по вертикали и по горизонтали перечисляются вершины. Если вершины смежны, на их пересечении в клетке ставится единица (1), если нет - 0.
С уважением.
Dron

Dron (статус: Студент), 2 февраля 2009, 19:15 [#5]:

Цитата (Milady):

Вооот! а как найти путь между заданными вершинами?

Вероятно, перебором. А как ещё? Не припомню, чтобы были какие-то действенные способы.
С уважением.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 10 апреля 2020, 04:07
Выполнено за 0.02 сек.
Рейтинг@Mail.ru