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

Задача "поиск кратчайшего пути в графе обходом в ширину(волновой алгоритм)" - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ произвидение матриц http://www.cyberforum.ru/cpp-beginners/thread593541.html
ребят помогите получить зачёт. 3 задачки осталось здать.решите плиз вот эту. найти произвидение матриц А(m;n) и В(n;k) С(M;k)=А*В. матрици А,В,С описать как одномерные массивы, используя приведённые индексы
C++ Расположение данных в стеке и в куче Друзья, возник вопрос. Следующий код char length_buffer; ...заполнение length_buffer двоичным представлением целого числа 999... int length = *reinterpret_cast<int *>(&length_buffer); работает. переменная length принимает значение 999. Но если четырехбайтовый массив расместить в куче, тоже самое двоичное значение перестает интерпретироваться как 999: char *length_buffer = new char;... http://www.cyberforum.ru/cpp-beginners/thread593538.html
Функция получает неотрицательную десятичную дробь и возвращает её представление в системе счисления с основанием р = 16 C++
Написать и протестировать функцию. Функция получает неотрицательную десятичную дробь и возвращает её представление в системе счисления с основанием р = 16. Помогите пожалуйста)
C++ [C++] Возведение дробного числа в дробную степень
Здравствуйте! Подскажите каким образом можно возвести дробное число в дробную степень? Например: 2.13.5 = 13.4205 pow(2.1, 3.5) и тому подобное не предлагать!
C++ Циклы с пред- и постусловим http://www.cyberforum.ru/cpp-beginners/thread593445.html
Помогите, пожалуйста, исправить. Рассчитайте e - основу натуральных логарифмов:e=\lim_{n\rightarrow \propto }n/ \sqrt{n!}. Определите при каком n значении впервые выполнится условие {e}_{n+1}-{e}_{n}\leq \varepsilon #include <stdio.h> #include <math.h> void main()
C++ Шаблон данных метода кдасса, наследование Eсть 3 класс 1 базовый 2 наследуемых, и функция... class Beast { public: int x; int y; int day; }; class Rabbit: public Beast{}; подробнее

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

Задача "поиск кратчайшего пути в графе обходом в ширину(волновой алгоритм)" - C++

01.06.2012, 17:17. Просмотров 2197. Ответов 0
Метки (Все метки)

Помогите с задачей поиск кратчайшего пути в графе обходом в ширину(волновой алгоритм)
Может у кого есть уже готовая? Или часть программы? Просто все что есть в интернете не понятно и сложно..
Вот один пример из интернета,здесь много не понятных функций и нет чтения самого графа:
Входные данные:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
vector < vector<int> > g; // граф
int n; // число вершин
int s; // стартовая вершина (вершины везде нумеруются с нуля)
 
// чтение графа
...
Сам обход:
 
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d (n), p (n);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to]) {
            used[to] = true;
            q.push (to);
            d[to] = d[v] + 1;
            p[to] = v;
        }
    }
}
Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины  , это можно сделать следующим образом:
 
if (!used[to])
    cout << "No path!";
else {
    vector<int> path;
    for (int v=to; v!=-1; v=p[v])
        path.push_back (v);
    reverse (path.begin(), path.end());
    cout << "Path: ";
    for (size_t i=0; i<path.size(); ++i)
        cout << path[i] + 1 << " ";
}

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