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

Задача с использованием алгоритма Дейкстры - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Разработать схему алгоритма для решения задачи численного интегрирования тремя методами http://www.cyberforum.ru/cpp-beginners/thread980079.html
Разработать схему алгоритма для решения задачи численного интегрирования с использованием метода прямоугольника, метода трапеций и метода Симпсона 4х2
C++ Как создать класс, где возможно создание только одного объекта? Как создать класс, где возможно создание только одного объекта? http://www.cyberforum.ru/cpp-beginners/thread980077.html
error C2678: бинарный ">>": не найден оператор, принимающий левый операнд типа "std::basic_istream<_Elem,_Traits>" C++
Нужно из файла скачать информацию в объект. Почему у меня не получается? #include <vector> #include <string> #include <iostream> #include <fstream> #include <iterator> using namespace std; class Money{
Текст из TXT файла в строку C++
Добрый день. С++ начал учить два дня назад, поэтому прошу не пинать за глупые вопросы. Ситуация следующая: есть строка S (типа char или string, пока не разобрался в чем конкретная разница) есть файл input.txt. В input.txt введен текст (для простоты возьмем что текст находится в одной строке). Задача: нужно текст из файла input.txt присвоить строке S, чтобы с ним можно было полноценно...
C++ Чьотов Чар http://www.cyberforum.ru/cpp-beginners/thread980058.html
#include <iostream> #include <Windows.h> #include <string.h> using namespace std; int main() { WIN32_FIND_DATAA findData; string file_name; cout << "Введите имя файла или q для выхода" << endl;
C++ Инкремент при обращении (н-р к массиву) int _id_; char _string_; _string_ // Изменится ли в этом случаее _id_ или это не повлеяет на начего? подробнее

Показать сообщение отдельно
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
17.10.2013, 18:04     Задача с использованием алгоритма Дейкстры
интересно было бы поглядеть что делает ваш готовый алгоритм Дейкстры. И вот почему.

Для решения вашей задачи нужно чтобы он заполнил массив, представляющий дерево кратчайших путей исходного графа (path), а также массив, содержащий время в пути до каждого города из исходого города i (dist).

Итак, алгоритм:
0. нужны матрица смежности для хранения карты дорог, 2 массива для хранения инфо о кратчайших путях в графе (как описано выше)
1. читаем input и заполняем матрицу смежности
2. применяем алгоритм Дейкстры, который заполнит те 2 массива
3. ответ для пункта а): время в пути - dist[ j ], сам путь восстанавливаем из массива path (правда он получится в обратном порядке, следовательно после восстановления его надо перевернуть)
4. ответ для пункта б): пробегаемся циклом по массиву dist и выводим те индексы массива, для которых dist равен искомому времени

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