Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Василий Алибабаевич
0 / 0 / 0
Регистрация: 17.12.2008
Сообщений: 1
#1

Поиск кратчашего пути в ненагруженном неорграфе от любой вершины до любой - C++

20.12.2008, 20:20. Просмотров 572. Ответов 0
Метки нет (Все метки)

Задача: необходимо найти кратчайший путь в ненагруженном неорграфе от любой вершины до любой.
Соображения: алгоритм Флойда не годится (О(n^3) - много). Общая идея - построение остовного дерева и определение пути с помощью оного. Кратчайший путь в данном случае находится с помощью глубинного обхода (вершина, от которой считается расстояние, объявляется корнем остовного дерева).
Просьба: скинуть код, если подобная задачка уже встречалась. Если нет таковой возможности - обрисовать идею программы поподробнее.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2008, 20:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск кратчашего пути в ненагруженном неорграфе от любой вершины до любой (C++):

Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0 - C++
Здравствуйте. Условие задачи, собственно, в названии темы. Возникли проблемы с алгоритмом, не говоря уже про код. Ограничений на входной...

Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа - C++
Здравствуйте! Есть задача найти самый длинный путь от первой до последней вершины ацикличного ориентированного невзвешенного графа....

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину - C++
В неориентированном графе требуется найти минимальный путь между двумя вершинами. Входные данные Первым на вход поступает число N –...

любой рисунок. - C++
Задание: 1.нарисовать на С++ любую картинку, 2 . наирсовать движущуюся картинку. Не могу ничего нарисовать. пытался паровоз, но то...

Перевод чисел из любой сс в 10-ую - C++
Задача: Программа должна переводить любое число в любой системе счисления (от унарной до десятичной включительно), которую задаст...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2008, 20:20
Привет! Вот еще темы с ответами:

Любой тип переменной - C++
Как указать переменной что тип неопределён? Допустим: struct STRUCTa{ short v1,v2; } struct STRUCTb{ float v1,v2; } ...

Выдает ошибку в любой программе - C++
Может я не достаточно внимателен, но посмотрите плз в чем дело. Вчера поставил ВС 2012 и теперь в любой программе абсолютно выдает ошибку :...

Калькулятор в любой системе счисления - C++
Добрый день, нужно написать что-то типа этого http://numsys.ru/#feedback. Подскажите пожалуйста, как реализовать двоичный-шестнадцатиричный...

Перевод чисел любой разрядности - C++
День добрый. Прошу помочь алгоритмом перевода чисел из одной системы счисления в другую - в данном случае из 8 в 10 и обратно - чисел...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.