Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.12.2013, 14:50   #1
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию (с++) Кратчайший путь в графе

Здравствуйте! Необходимо вывести на экран кратчайший путь от одной вершины графа до другой, методом обхода в ширину. Составил программу, но она выводит весь обход до вершины (т.е. есть 3 смежных вершины - 1, 2 и 3, путь от 1 до 3 выводит как 1-2-3 (весь обход), а не кратчайший 1-3)
Код:
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <queue>
using namespace std;
queue<int> my;
int mat [4][4] = 
	{
		0, 1, 1, 0,
		0, 0, 1, 0,
		1, 0, 0, 1,
		0, 1, 0, 0,
	};
int was [4]; //массив, отображающий посещена ли вершина

void BFS (int start, int finish)
{
	int cur;
	my.push (start);
	while (!my.empty())
	{
		cur = my.front();
		cout << cur << " ";
		my.pop();
		if (cur == finish)
		{
			cout << " Конечная вершина найдена!";
			return;
		}
		if (was[cur] == 1)
			return;
		was[cur] = 1;
		for (int i=0; i<4; i++)
			if(mat[cur][i])
				my.push (i);
	
	}

}


int main()
{
	setlocale (0, "");
	
	int start, finish;
	for (int i=0; i<5; i++)
		was[i]=0;
	cout << "Введите начальную и конечную вершины: ";
	cin >> start >> finish;
	BFS (start,  finish);

getch();
}
Uefa вне форума Ответить с цитированием
Старый 03.12.2013, 05:00   #2
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию

тема актуальна
Uefa вне форума Ответить с цитированием
Старый 03.12.2013, 13:00   #3
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию

никто не знает?
Uefa вне форума Ответить с цитированием
Старый 03.12.2013, 13:48   #4
SaLoKiN
Форумчанин
 
Аватар для SaLoKiN
 
Регистрация: 19.09.2013
Сообщений: 597
По умолчанию

если нужно вывести корень и конечный узел,тогда:
пока не конец дерева
посетил уровень- значение узла в некую переменную.
вывод корня - вывод переменной
UPD посмотрел код программы, и не понял что нужно опять)
пример приведите пожалста)
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!!

Последний раз редактировалось SaLoKiN; 03.12.2013 в 13:51.
SaLoKiN вне форума Ответить с цитированием
Старый 03.12.2013, 15:32   #5
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию

Цитата:
Сообщение от SaLoKiN Посмотреть сообщение
если нужно вывести корень и конечный узел,тогда:
пока не конец дерева
посетил уровень- значение узла в некую переменную.
вывод корня - вывод переменной
UPD посмотрел код программы, и не понял что нужно опять)
пример приведите пожалста)
Задание: разработать для решения поставленной задачи алгоритм, используя поиск в ширину. Найти кратчайший путь из точки A в точку B. Тип графа: неориентированный невзвешенный
Uefa вне форума Ответить с цитированием
Старый 04.12.2013, 05:47   #6
SaLoKiN
Форумчанин
 
Аватар для SaLoKiN
 
Регистрация: 19.09.2013
Сообщений: 597
По умолчанию

Цитата:
Составил программу, но она выводит весь обход до вершины (т.е. есть 3 смежных вершины - 1, 2 и 3, путь от 1 до 3 выводит как 1-2-3 (весь обход), а не кратчайший 1-3)
пока вы не покажете пример вашего графа с вершинами 1-2-3 я не смогу помочь.
если граф у вас вида
1
2 3
а найти путь от 1 до 3, тогда при обходе в ширину кратчайший путь будет 1-2-3.
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!!
SaLoKiN вне форума Ответить с цитированием
Старый 04.12.2013, 05:52   #7
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию

Обход в ширину графа позволяет найти кратчайший путь от одной вершины к другой, в моей программе выводится весь обход графа (т.е. сначала проверяются смежные со стартовой вершины, если среди них нет конечной, начинаем проверять смежные со смежными и так по порядку), мне нужно сделать чтобы выводился только кратчайший путь, а не весь обход!
Uefa вне форума Ответить с цитированием
Старый 04.12.2013, 05:55   #8
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию

Цитата:
Сообщение от SaLoKiN Посмотреть сообщение
пока вы не покажете пример вашего графа с вершинами 1-2-3 я не смогу помочь.
если граф у вас вида
1
2 3
а найти путь от 1 до 3, тогда при обходе в ширину кратчайший путь будет 1-2-3.
Вы правильно поняли проблему. Только везде написано, что обход в ширину находит кратчайший путь, а в данном случае кратчайший 1-3, т.е. вывести 1-3 с помощью данного обхода нереально?
Uefa вне форума Ответить с цитированием
Старый 04.12.2013, 06:03   #9
Uefa
Пользователь
 
Регистрация: 25.08.2013
Сообщений: 59
По умолчанию


Последний раз редактировалось Uefa; 04.12.2013 в 06:07.
Uefa вне форума Ответить с цитированием
Старый 04.12.2013, 07:03   #10
SaLoKiN
Форумчанин
 
Аватар для SaLoKiN
 
Регистрация: 19.09.2013
Сообщений: 597
По умолчанию

а разве для такой картинки матрица смежности будет такой?
0, 1, 1, 0,
0, 0, 1, 0,
1, 0, 0, 1,
0, 1, 0, 0,
и вроде для нахождения кратчайшего пути граф должен быть взвешенный...или нужно найти путь по минимальному количеству пройденных вершин от start to end?
Сделал сам, помоги другому!
Что-то работает не так? Дебаггер в помощь!!!

Последний раз редактировалось SaLoKiN; 04.12.2013 в 07:08.
SaLoKiN вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Кратчайший путь Delphi zzzzz Помощь студентам 1 27.06.2012 07:39
Кратчайший путь от одной точки до другой. firephenix Помощь студентам 3 05.06.2011 00:30
Кратчайший путь к точке W0LF Общие вопросы Delphi 3 17.05.2011 15:40
Кратчайший путь между двум вершинами Gapro Общие вопросы C/C++ 4 04.11.2010 20:24
Найти кратчайший путь между точками lucky Общие вопросы Delphi 0 27.05.2009 07:26