|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
31.05.2009, 20:04 | #1 |
Пользователь
Регистрация: 29.10.2008
Сообщений: 15
|
поиск кратчайшего пути проходящий через ВСЕ города C++
Имеется n городов. Некоторые из них соединины дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент a(ij)который равен некоторому трицательному числу, если город i не соединен напрямую дорогой с городом j и равено длине дороги, впротивном случае (i,j = 1,..., n). В предположении, что каждый город соединен напрямую с дорогой с каждым, найти кратчайший маршрут начинающийся в 1-ом городе и проходящий через все остальные. С++
такое решается?? в инете МНОГО всего нашёл, когда кратчайший путь путь из однго в другой, а через все нету алгоритм хотябы предложите какойнить |
31.05.2009, 20:17 | #2 |
Eclipse Foundation
Старожил
Регистрация: 19.09.2007
Сообщений: 2,604
|
Обход графа в глубину:
Алгоритм: У вас есть два стека: Стек пройденных вершин и стек смежных вершин. 1. Заносите начальную точку в стек пройденных вершин. 2. Заносите в стек смежных вершин, все смежные вершины 3. Проверяете последнюю из занесенных смежных вершин на "проверенность", если она еще не проверена, то заносим ее в стек пройденных вершин, и начинаем алгоритм с этой вершины. Алгоритм заканчивается, когда будут пройдены все вершины графа. Обход графа в ширину: Список пройденных вершин и очередь смежных вершин. 1. Заносим первую вершину в список провернных вершин. 2. В очередь заносим все смежные вершины 3. Проверяем каждую смежную вершину в очереди на "проверенность" 4. Заносим в список пройденных все смежные вершины 5. Последняя в очереди смежная вершина - становится начальной 6. Цикл повторяется до тех пор, пока все вершины не будут пройдены А про кратчайший путь - Алгоритм Дейкстры. |
02.06.2009, 21:21 | #3 |
Пользователь
Регистрация: 29.10.2008
Сообщений: 15
|
тут смежнные вершины не причём. каждый кород СВЯЗАН с каждым!!!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | Shady | Помощь студентам | 5 | 06.10.2014 18:29 |
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ | Олинька | Помощь студентам | 1 | 24.12.2008 16:22 |
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) | Serega123 | Помощь студентам | 3 | 30.10.2008 22:26 |
применить Алгоритм Дейкстры для поиска кратчайшего пути в графе | Эдгар | Microsoft Office Excel | 13 | 24.10.2008 21:01 |