Кратчайший путь между двум вершинами - Общие вопросы C/C++

Gapro · 01.11.2010, 19:51

Помогите плиз с решением куска задачи:
У меня есть массив векторов g[5000] с описанием графа, нгужно найти кратчайшее расстояние между вершиной 1 и вершиной n. Уже полчаса гуглил, никакого конкретного кода не нашел.

raxp · 01.11.2010, 22:05

посмотрите в сторону алгоритма Дейкстры, например ...очень доходчиво об этом в статье Уткина в №3 журнала нашего Клуба (см. подпись), думаю проблем с переводом на си при понимании самих принципов у вас не возникнет.

Gapro · 02.11.2010, 19:22

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

raxp · 02.11.2010, 22:03

лучше статью почитайте.

Gapro · 04.11.2010, 20:24

Статью почитал, потом погуглил и понял, что в моем случае больше волновой алгоритм подходит, сейчас думаю над его реализацией.

01.11.2010, 19:51	#1
Gapro Форумчанин Регистрация: 30.07.2009 Сообщений: 256	Кратчайший путь между двум вершинами Помогите плиз с решением куска задачи: У меня есть массив векторов g[5000] с описанием графа, нгужно найти кратчайшее расстояние между вершиной 1 и вершиной n. Уже полчаса гуглил, никакого конкретного кода не нашел.

01.11.2010, 22:05	#2
raxp Старожил Регистрация: 29.09.2009 Сообщений: 9,713	посмотрите в сторону алгоритма Дейкстры, например ...очень доходчиво об этом в статье Уткина в №3 журнала нашего Клуба (см. подпись), думаю проблем с переводом на си при понимании самих принципов у вас не возникнет. Разработки и научно-технические публикации :: Видеоблог :: Твиттер Radar systems engineer & Software developer of industrial automation

02.11.2010, 22:03	#4
raxp Старожил Регистрация: 29.09.2009 Сообщений: 9,713	лучше статью почитайте. Разработки и научно-технические публикации :: Видеоблог :: Твиттер Radar systems engineer & Software developer of industrial automation

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
кратчайшие расстояния между вершинами	pum-pum-pum	Помощь студентам	1	07.01.2010 11:30
Кратчайшее расстояние между всеми вершинами	ooooch	Помощь студентам	5	15.11.2009 15:36
Графы (кратчайший путь и обход ВСЕХ вершин)	08ekhiv1	Помощь студентам	5	05.08.2009 13:12
Найти кратчайший путь между точками	lucky	Общие вопросы Delphi	0	27.05.2009 07:26

02.11.2010, 19:22	#3
Gapro Форумчанин Регистрация: 30.07.2009 Сообщений: 256	Дейкстру то я понимаю примерно на уровне псевдокода, но не могу закодить так, чтобы ф-я мне возвращала путь от начальной вершины до искомой вершины, т.е. получается массив предков искомой вершины, относительно начальной.

04.11.2010, 20:24	#5
Gapro Форумчанин Регистрация: 30.07.2009 Сообщений: 256	Статью почитал, потом погуглил и понял, что в моем случае больше волновой алгоритм подходит, сейчас думаю над его реализацией.