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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Использование libopencm3 http://www.cyberforum.ru/cpp-beginners/thread1514526.html
Добрый день. Пытаюсь запустить пример к библиотеке libopencm3. Есть объявленная структура: struct usb_config_descriptor { uint8_t bLength; uint8_t bDescriptorType; uint16_t wTotalLength; uint8_t bNumInterfaces;
C++ Кольцевой список STL Добрый день, такой вопрос: можно ли работать с STL-списком как с кольцевым? Если да, то как? Нигде не нашел в литературе. http://www.cyberforum.ru/cpp-beginners/thread1514507.html
C++ Откуда cmd берет тайлы букв?
читаю форум, в соседней ветке обсуждают коды нажатия клавиш клавиатуры. подумал, как происходит рисование в командной строке, в том числе рисование тайлов букв (т.е. какой-нибудь текстовый редактор сделать) кто что может подсказать по данной теме? заранее спасибо
Форма документа о продаже товаров C++
Помогите, пожалуйста. Не знаю как написать по этому программу Информация о продаже товаров подготовлена по следующему макету: номер магазина; номер секции; номер чека; наименование товара; артикул товара; цена товара; количество то- вара; дата продажи. Составить программу определения объема товарооборота по каждому ма- газину, т.е. общую сумму, вырученную от продажи всех товаров в данном...
C++ Где хранит свои данные vector? http://www.cyberforum.ru/cpp-beginners/thread1514458.html
class A { class B{...} vector<B> vec; foo1() { vec.emplace_back(B()); }
C++ Что почитать для обучения В недавнем времени изучил html и css и мне стали интересны компьютеры,но делать сайты не хочу, и начал изучать c++,но насколько я понял,кроме самого c++ нужно знать алгоритмы и что-то ещё,я не знаю...Хочу вообще математику подтянуть (дискретная наверное нужна),потом в ОС начать разбираться ,архитекуре компьютера и сетях Подскажите что почитать Есть книги Танненбаума и Хаггарти(из серии... подробнее

Показать сообщение отдельно
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
14.08.2015, 20:01
Цитата Сообщение от Catstail Посмотреть сообщение
Dani, дело не в этом. Когда мы начинаем поиск в ширину с вершины А и доходим до вершины B, путь будет кратчайшим. Поиск в глубину этого не гарантирует.
При поиске в глубину можно идти в вершину не в том случае, если она не посещена, а в том, если мы улучшаем расстояние. Пример:
C++
1
2
3
4
5
6
7
8
9
10
11
int d[VERTEX_COUNT];
std::fill(d, d + VERTEX_COUNT, INFINITY);
void DFS(int v, int way = 0) //v - номер вершины, way - длина пути до нее
{
     d[v] = way;
     for(int i = 0; i < graph[v].size(); ++i)
       if(d[ graph[v][i] ] > v + 1) DFS(graph[v][i], v + 1);
} 
...
DFS(start);
std::cout << d[finish];
Теперь мы по-любому получим оптимальный маршрут. Но можно подобрать такой граф, на котором эта программа будет работать долго.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru