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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Поиск в строке по образцу. http://www.cyberforum.ru/cpp-beginners/thread19103.html
Подсчитайте количество указанных цепочек в файле, найденных по образцу. Причем в образце символ "+" означает один произвольный символ, а символ "*" – произвольную цепочку длиной не более 5 символов....
C++ Напишите программу, вычисляющую стоимость покупки с учетом скидки. Помогите решить 4 задачи: :wall:1) Известно, что оптимальный вес вычисляется по форуме: рост(в сантиметрах) - 100.Напишите программу, которая вычисляет оптимальный вес и выдает рекомендации. ... http://www.cyberforum.ru/cpp-beginners/thread19102.html
Работа со стуктурой и файлами C++
Есть задачка, состоит с двух частей. Превую часть я сделал: Создать структуру, чтоб можна было добавлять данные , удалять, поиск за заданым елементом, выводить на екран всю структуру, запись в файл и...
C++ строки в файле должны перевернуться вверх-ногами
есть файл со строками, строки должны перевернуться вверх-ногами, сделать нужно с помощью классов.:help:
C++ Дан файл с текстом, нужно чтоб от текста остались только четные цифры. http://www.cyberforum.ru/cpp-beginners/thread19094.html
Дан файл с текстом, нужно чтоб от текста остались только четные цифры. Делать задали с помощью классов. Помогите плз.
C++ Упорядочить элементы 2х файлов Вобщем такая задача: Даны 2 файла в каждом элементы, упорядоченные по невозрастанию.Требуется упорядочить их и сохранить в третий файл. Сделал вот так: #include <stdio.h> #include <stdlib.h>... подробнее

Показать сообщение отдельно
Василий Алибабаевич
Сообщений: n/a

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

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

Задача: необходимо найти кратчайший путь в ненагруженном неорграфе от любой вершины до любой.
Соображения: алгоритм Флойда не годится (О(n^3) - много). Общая идея - построение остовного дерева и определение пути с помощью оного. Кратчайший путь в данном случае находится с помощью глубинного обхода (вершина, от которой считается расстояние, объявляется корнем остовного дерева).
Просьба: скинуть код, если подобная задачка уже встречалась. Если нет таковой возможности - обрисовать идею программы поподробнее.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru