![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
Здравствуйте! Необходимо вывести на экран кратчайший путь от одной вершины графа до другой, методом обхода в ширину. Составил программу, но она выводит весь обход до вершины (т.е. есть 3 смежных вершины - 1, 2 и 3, путь от 1 до 3 выводит как 1-2-3 (весь обход), а не кратчайший 1-3)
Код:
|
![]() |
![]() |
![]() |
#2 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
тема актуальна
|
![]() |
![]() |
![]() |
#3 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
никто не знает?
![]() |
![]() |
![]() |
![]() |
#4 |
Форумчанин
Регистрация: 19.09.2013
Сообщений: 597
|
![]()
если нужно вывести корень и конечный узел,тогда:
пока не конец дерева посетил уровень- значение узла в некую переменную. вывод корня - вывод переменной UPD посмотрел код программы, и не понял что нужно опять) пример приведите пожалста)
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!! Последний раз редактировалось SaLoKiN; 03.12.2013 в 13:51. |
![]() |
![]() |
![]() |
#5 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
Задание: разработать для решения поставленной задачи алгоритм, используя поиск в ширину. Найти кратчайший путь из точки A в точку B. Тип графа: неориентированный невзвешенный
|
![]() |
![]() |
![]() |
#6 | |
Форумчанин
Регистрация: 19.09.2013
Сообщений: 597
|
![]() Цитата:
если граф у вас вида 1 2 3 а найти путь от 1 до 3, тогда при обходе в ширину кратчайший путь будет 1-2-3.
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!! |
|
![]() |
![]() |
![]() |
#7 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
Обход в ширину графа позволяет найти кратчайший путь от одной вершины к другой, в моей программе выводится весь обход графа (т.е. сначала проверяются смежные со стартовой вершины, если среди них нет конечной, начинаем проверять смежные со смежными и так по порядку), мне нужно сделать чтобы выводился только кратчайший путь, а не весь обход!
|
![]() |
![]() |
![]() |
#8 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]()
Вы правильно поняли проблему. Только везде написано, что обход в ширину находит кратчайший путь, а в данном случае кратчайший 1-3, т.е. вывести 1-3 с помощью данного обхода нереально?
|
![]() |
![]() |
![]() |
#9 |
Пользователь
Регистрация: 25.08.2013
Сообщений: 59
|
![]() ![]() Последний раз редактировалось Uefa; 04.12.2013 в 06:07. |
![]() |
![]() |
![]() |
#10 |
Форумчанин
Регистрация: 19.09.2013
Сообщений: 597
|
![]()
а разве для такой картинки матрица смежности будет такой?
0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, и вроде для нахождения кратчайшего пути граф должен быть взвешенный...или нужно найти путь по минимальному количеству пройденных вершин от start to end?
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!! Последний раз редактировалось SaLoKiN; 04.12.2013 в 07:08. |
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Кратчайший путь Delphi | zzzzz | Помощь студентам | 1 | 27.06.2012 07:39 |
Кратчайший путь от одной точки до другой. | firephenix | Помощь студентам | 3 | 05.06.2011 00:30 |
Кратчайший путь к точке | W0LF | Общие вопросы Delphi | 3 | 17.05.2011 15:40 |
Кратчайший путь между двум вершинами | Gapro | Общие вопросы C/C++ | 4 | 04.11.2010 20:24 |
Найти кратчайший путь между точками | lucky | Общие вопросы Delphi | 0 | 27.05.2009 07:26 |