Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1. - C++

@Mr_Blam · Регистрация: 23.12.2010

Помогите с программным кодом на c++

Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1. Нужно определить все возможные маршруты между исходным пунктом и всеми остальными пунктами. Собственно, результат вывести на экран.

@ForEveR · 23.12.2010, 02:02

Алгоритм Дейкстры в руки и вперед.
Или можно Флойда-Уоршалла

@Mr_Blam · 23.12.2010, 02:05 **[ТС]**

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

Алгоритм Дейкстры в руки и вперед.
Или можно Флойда-Уоршалла

Извините, но пока еще не знаком, не с одним из них((

В чем заключается его сущность применительно к данной программе?

@ForEveR · 23.12.2010, 02:08

Mr_Blam, А вбить в поисковике и посмотреть?

@Mr_Blam · 23.12.2010, 02:15 **[ТС]**

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

Mr_Blam, А вбить в поисковике и посмотреть?

уже посмотрел, Алгоритм Дейкстры решает задачу о кратчайших путях, мне же необходимо отыскать всевозможные... также, расстояние между пунктами не есть равноудаленное

@ForEveR · 23.12.2010, 02:18

Кратчайшие пути как ни странно не ищутся между равноудаленными пунктами...
А вот на тему всех путей - действительно я промахнулся.

@Mr_Blam · 23.12.2010, 04:34 **[ТС]**

Да уж, походу эта задача так и останется мною непонятая... (

valeriikozlov · 23.12.2010, 09:25

Немного странная формулировка задания:

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

Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1. Нужно определить все возможные маршруты между исходным пунктом и всеми остальными пунктами. Собственно, результат вывести на экран.

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

Задан исходный пункт, различные пункты посещения, информация о наличии связи между пунктами i и i+1. Нужно определить все возможные маршруты между исходным пунктом и всеми остальными пунктами (пунктами посещения). Собственно, результат вывести на экран.

и задан граф без циклов.

@CyberHunter · 23.12.2010, 09:59

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

Если есть циклы, то скорее всего кол-во все возможных маршрутов будет бесконечно.

Не скорее всего, а точно, если не стоит ограничение на количество остановок, время и прочее, самый простой вариант - если ехать из Владивостока в Москву, то можно проехать Новосибирск, Омск, а можно несколько раз по пути заехать из Новосибирска в Омск потом обратно в Новосибирск, так можно сделать 10 раз, а можно и 1000, для постановки задачи необходимо задать количество остановок по пути или выводить на экран всевозможные маршруты можно до бесконечности...

valeriikozlov · 23.12.2010, 11:37

CyberHunter, Я не зря написал

скорее всего

. Если цикл всего один и все вершины графа находятся на нем, то путей будет всего два.

@ForEveR В астрале 7994 / 4753 / 651 Регистрация: 24.06.2010 Сообщений: 10,547 Завершенные тесты: 3
	23.12.2010, 02:02	#2
	Алгоритм Дейкстры в руки и вперед. Или можно Флойда-Уоршалла 0

@Mr_Blam 0 / 0 / 0 Регистрация: 23.12.2010 Сообщений: 4
	23.12.2010, 02:05 [ТС]	#3
	Сообщение от ForEveR Алгоритм Дейкстры в руки и вперед. Или можно Флойда-Уоршалла Извините, но пока еще не знаком, не с одним из них(( В чем заключается его сущность применительно к данной программе? 0

@ForEveR В астрале 7994 / 4753 / 651 Регистрация: 24.06.2010 Сообщений: 10,547 Завершенные тесты: 3
	23.12.2010, 02:08	#4
	Mr_Blam, А вбить в поисковике и посмотреть? 0

@Mr_Blam 0 / 0 / 0 Регистрация: 23.12.2010 Сообщений: 4
	23.12.2010, 02:15 [ТС]	#5
	Сообщение от ForEveR Mr_Blam, А вбить в поисковике и посмотреть? уже посмотрел, Алгоритм Дейкстры решает задачу о кратчайших путях, мне же необходимо отыскать всевозможные... также, расстояние между пунктами не есть равноудаленное 0

@ForEveR В астрале 7994 / 4753 / 651 Регистрация: 24.06.2010 Сообщений: 10,547 Завершенные тесты: 3
	23.12.2010, 02:18	#6
	Кратчайшие пути как ни странно не ищутся между равноудаленными пунктами... А вот на тему всех путей - действительно я промахнулся. 0

@Mr_Blam 0 / 0 / 0 Регистрация: 23.12.2010 Сообщений: 4
	23.12.2010, 04:34 [ТС]	#7
	Да уж, походу эта задача так и останется мною непонятая... ( 0

valeriikozlov 4683 / 2509 / 751 Регистрация: 18.08.2009 Сообщений: 4,550
	23.12.2010, 09:25	#8
	Сообщение было отмечено как решение Решение Немного странная формулировка задания: Сообщение от Mr_Blam Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1. Нужно определить все возможные маршруты между исходным пунктом и всеми остальными пунктами. Собственно, результат вывести на экран. Если между двумя пунктами есть несколько путей, значит в графе есть циклы. Если есть циклы, то скорее всего кол-во все возможных маршрутов будет бесконечно. Может быть задание звучит так?: Задан исходный пункт, различные пункты посещения, информация о наличии связи между пунктами i и i+1. Нужно определить все возможные маршруты между исходным пунктом и всеми остальными пунктами (пунктами посещения). Собственно, результат вывести на экран. и задан граф без циклов. 0

@CyberHunter 13 / 13 / 1 Регистрация: 03.08.2010 Сообщений: 61
	23.12.2010, 09:59	#9
	Сообщение от valeriikozlov Если есть циклы, то скорее всего кол-во все возможных маршрутов будет бесконечно. Не скорее всего, а точно, если не стоит ограничение на количество остановок, время и прочее, самый простой вариант - если ехать из Владивостока в Москву, то можно проехать Новосибирск, Омск, а можно несколько раз по пути заехать из Новосибирска в Омск потом обратно в Новосибирск, так можно сделать 10 раз, а можно и 1000, для постановки задачи необходимо задать количество остановок по пути или выводить на экран всевозможные маршруты можно до бесконечности... 0

valeriikozlov 4683 / 2509 / 751 Регистрация: 18.08.2009 Сообщений: 4,550
	23.12.2010, 11:37	#10
	CyberHunter, Я не зря написал скорее всего . Если цикл всего один и все вершины графа находятся на нем, то путей будет всего два. 0

Опции темы

Задан исходный маршрут, различные пункты посещения, информация о наличии связи между пунктами i и i+1. - C++

Решение