Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 15:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru