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

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

Восстановить пароль Регистрация
 
kinivi
0 / 0 / 0
Регистрация: 13.08.2015
Сообщений: 5
14.08.2015, 11:26     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #1
В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Входные данные
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

Выходные данные
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Если пути нет, нужно вывести -1.
Код
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int> > edges;
vector <int> doroga;
 
int start;
int d[100],mark[100],m[100][100],v[100],p[100];
void BFS()
{
    queue<int> q;
    // Инициализация: есть информация про начальную вершину
    q.push(start);
    p[start]=-1;
    d[start] = 0;
    mark[start] = 1;
    // Главный цикл - пока есть серые вершины
    while (!q.empty())
    {
        // Берем первую из них
        int v = q.front();
        q.pop();
        // Пробегаемся по всем ее соседям
        for (int i = 0; i < (int)edges[v].size(); ++i)
        {
            // Если сосед белый
            if (mark[edges[v][i]] == 0)
            {
                // То вычисляем расстояние
                d[edges[v][i]] = d[v] + 1;
                p[edges[v][i]]= v;
                // И он становится серым
                mark[edges[v][i]] = 1;
                q.push(edges[v][i]);
            }
        }
    }
}
 
int main()
{
setlocale(LC_ALL, "Rus");
int n,k,en,st;
cin>>n;
edges.resize(n);
for(int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    cin>>m[i][j];
 
for (int i=0;i<n;i++) {k=0;
    for (int j=0;j<n;j++)
    if ( m[i][j] ==1) { edges[i].push_back(j);k++;}
}
cin>>st>>en;
start=st-1;
 
BFS();
if (!mark) cout<<-1; else if (en==st) cout<<0; else {
cout<<d[en-1];
cout<<endl;
 
 
    for (int v=en;v!=-1;v=p[v]) doroga.push_back(v+1);
 
    for(int i=doroga.size()-1;i>0;i--) cout<<doroga[i]<<' ';
cout<<en;
}
 
 
 
 
 
 
}
На сайте informatics проходит только 6 тестов (остальные это ошибка: неправильный формат вывода). В коде меня смущает то что конечный елемент пути (p[en]=5 не 4 как это должно быть)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.08.2015, 11:26     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину
Посмотрите здесь:

Поиск самых коротких расстояний между любыми двумя вершинами графа по методу Шимбела C++
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Найти все пути между двумя любыми вершинами в графе C++
Нужно определить количество путей между двумя вершинами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
14.08.2015, 11:44     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #2
Цитата Сообщение от kinivi Посмотреть сообщение
for (int v=en;v!=-1;v=p[v]) doroga.push_back(v+1);
Вероятно int v = en-1
Catstail
Модератор
 Аватар для Catstail
21435 / 10220 / 1666
Регистрация: 12.02.2012
Сообщений: 17,095
14.08.2015, 11:49     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #3
Даже не глядя в код, могу сказать: для поиска кратчайшего пути от вершины A до B нужно использовать не поиск в глубину, а поиск в ширину.
kinivi
0 / 0 / 0
Регистрация: 13.08.2015
Сообщений: 5
14.08.2015, 11:51  [ТС]     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #4
Извините там поиск в ширину. тему неправильно назвал
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
14.08.2015, 12:31     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #5
Цитата Сообщение от Catstail Посмотреть сообщение
Даже не глядя в код, могу сказать: для поиска кратчайшего пути от вершины A до B нужно использовать не поиск в глубину, а поиск в ширину.
Поиск в глубину тоже можно использовать в принципе, но это будет дольше
Catstail
Модератор
 Аватар для Catstail
21435 / 10220 / 1666
Регистрация: 12.02.2012
Сообщений: 17,095
14.08.2015, 13:15     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #6
Dani, дело не в этом. Когда мы начинаем поиск в ширину с вершины А и доходим до вершины B, путь будет кратчайшим. Поиск в глубину этого не гарантирует.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2015, 20:01     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину
Еще ссылки по теме:

Граф - существует ли связь между двумя вершинами в обоих направлениях C++
C++ Графы, нахождение наименьшего пути между вершинами обходом в ширину
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
14.08.2015, 20:01     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину #7
Цитата Сообщение от 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];
Теперь мы по-любому получим оптимальный маршрут. Но можно подобрать такой граф, на котором эта программа будет работать долго.
Yandex
Объявления
14.08.2015, 20:01     Найти минимальный путь между двумя вершинами в неорграфе. Поиск в ширину
Ответ Создать тему
Опции темы

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