Выясните, есть ли в данном графе вершина, расстояние от которой до каждой вершины не превышает k

@kosntain · Регистрация: 16.06.2015

Студворк — интернет-сервис помощи студентам

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

Логически все понятно, а как писать сам код - нет, предварительно не объясняли как работать с этими графами.
Помогите пожалуйста, натолкните хотя бы на путь правильный, какой тут алгоритм должен быть, может подойдет стандартный какой-то, как что описать.
Задача из первого курса, думаю что у опытных людей трудностей не возникло бы. Спасибо.

ФедосеевПавел · 16.06.2015, 23:03

Алгоритм Флойда-Уоршалла на выходе даст матрицу кратчайших расстояний между всеми парами вершин.
Эту матрицу и проверишь строка за строкой на предмет выполнения условия.

Дальше будет сложнее, поэтому читай, разбирайся.

@kosntain · 17.06.2015, 14:16 **[ТС]**

Спасибо, алгоритм понял, но я не знаю как его реализовать(

@Puporev · 17.06.2015, 14:25

Сообщение от kosntain

но я не знаю как его реализовать(

Посмотри здесь
http://kvodo.ru/algoritm-floyda-uorshella.html

@kosntain · 17.06.2015, 17:14 **[ТС]**

Посмотрел, спасибо, в самом алгоритме разобрался вроде, но ещё один небольшой вопрос по поводу того как сравнивать с k то что получается, можно немного объяснить?

@Puporev · 17.06.2015, 17:16

Сообщение от kosntain

как сравнивать с k то что получается,

Вам же написали

Сообщение от ФедосеевПавел

Эту матрицу и проверишь строка за строкой на предмет выполнения условия.

Если такое не умеете, то кто поверит что поняли Алгоритм Флойда-Уоршалла

@kosntain 0 / 0 / 0 Регистрация: 16.06.2015 Сообщений: 3
		1
	Выясните, есть ли в данном графе вершина, расстояние от которой до каждой вершины не превышает k 16.06.2015, 18:01. Показов 680. Ответов 5 Метки нет (Все метки) Помогите написать программу Сама задача: Даны связный неориентированный взвешенный граф и натуральное число k. Выясните, есть ли в данном графе вершина, расстояние от которой до каждой вершины не превышает k. Логически все понятно, а как писать сам код - нет, предварительно не объясняли как работать с этими графами. Помогите пожалуйста, натолкните хотя бы на путь правильный, какой тут алгоритм должен быть, может подойдет стандартный какой-то, как что описать. Задача из первого курса, думаю что у опытных людей трудностей не возникло бы. Спасибо. 0

ФедосеевПавел Модератор 8389 / 4266 / 1623 Регистрация: 01.02.2015 Сообщений: 13,285 Записей в блоге: 5
	16.06.2015, 23:03	2
	Алгоритм Флойда-Уоршалла на выходе даст матрицу кратчайших расстояний между всеми парами вершин. Эту матрицу и проверишь строка за строкой на предмет выполнения условия. Дальше будет сложнее, поэтому читай, разбирайся. 1

@kosntain 0 / 0 / 0 Регистрация: 16.06.2015 Сообщений: 3
	17.06.2015, 14:16 [ТС]	3
	Спасибо, алгоритм понял, но я не знаю как его реализовать( 0

@Puporev Почетный модератор 64291 / 47589 / 32740 Регистрация: 18.05.2008 Сообщений: 115,181
	17.06.2015, 14:25	4
	Сообщение от kosntain но я не знаю как его реализовать( Посмотри здесь http://kvodo.ru/algoritm-floyda-uorshella.html 0

@kosntain 0 / 0 / 0 Регистрация: 16.06.2015 Сообщений: 3
	17.06.2015, 17:14 [ТС]	5
	Посмотрел, спасибо, в самом алгоритме разобрался вроде, но ещё один небольшой вопрос по поводу того как сравнивать с k то что получается, можно немного объяснить? 0

@Puporev Почетный модератор 64291 / 47589 / 32740 Регистрация: 18.05.2008 Сообщений: 115,181
	17.06.2015, 17:16	6
	Сообщение от kosntain как сравнивать с k то что получается, Вам же написали Сообщение от ФедосеевПавел Эту матрицу и проверишь строка за строкой на предмет выполнения условия. Если такое не умеете, то кто поверит что поняли Алгоритм Флойда-Уоршалла 0

Опции темы