Number
1

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

01.06.2012, 17:17. Показов 3636. Ответов 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 << " ";
}

Заранее спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.06.2012, 17:17
Ответы с готовыми решениями:

Нужен исх. "поиск кратчайшего пути на графе"
помогите плиз.

Волновой алгоритм поиска кратчайшего пути
Доброго времени суток. Помогите пожалуйста решить задание. Необходимо составить(и желательно,...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2...

Генетический алгоритм поиска кратчайшего пути в графе
Преподаватель дал вот такое задание : &quot;Распараллелить генетический алгоритм на куда, а алгоритм...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.06.2012, 17:17

Нахождение кратчайшего пути в графе (алгоритм Дейкстры)
Здравствуйте, помогите пожалуйста, СРОЧНО,написать псевдокод реализации нахождения кратчайшего пути...

Поиск кратчайшего пути в графе
помогите сделать так чтобы в весе графа можно было вписывать не только целый числа, но и дробные....

Поиск кратчайшего пути в графе
Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую задачу в...

Поиск кратчайшего пути в графе
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном ациклическом...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru