Графы

@JamesBlack · Регистрация: 28.07.2009

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

Суть задачи: дан ориентированный граф, у которого каждая вершина (не ребро) имеет вес. Нужно найти путь из любой точки в любую, но чтобы он набирал наибольший вес. Дважды проходить через точки нельзя.
Никто не знает алгоритма, который мог бы помочь? Просто решение задачи "в лоб", перебором - это настоящий мазохизм!

Добавлено через 10 минут
Если можете, дайте сайт, на котором подобный алгоритм можно было бы найти. Пожалуйста! Я неделю мозги ломал, пытался свой придумать.

Добавлено через 18 минут
ап

@CheshireCat · 07.05.2010, 23:24

Гугли по лексемам "алгоритм Дейкстры" или "волновой алгоритм".

@JamesBlack · 07.05.2010, 23:26 **[ТС]**

наконец-то, хоть какая-то зацепка! Спасиб!

@JamesBlack 46 / 46 / 5 Регистрация: 28.07.2009 Сообщений: 144
		1
	Графы 07.05.2010, 22:59. Показов 919. Ответов 2 Метки нет (Все метки) Суть задачи: дан ориентированный граф, у которого каждая вершина (не ребро) имеет вес. Нужно найти путь из любой точки в любую, но чтобы он набирал наибольший вес. Дважды проходить через точки нельзя. Никто не знает алгоритма, который мог бы помочь? Просто решение задачи "в лоб", перебором - это настоящий мазохизм! Добавлено через 10 минут Если можете, дайте сайт, на котором подобный алгоритм можно было бы найти. Пожалуйста! Я неделю мозги ломал, пытался свой придумать. Добавлено через 18 минут ап 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	07.05.2010, 23:24	2
	Гугли по лексемам "алгоритм Дейкстры" или "волновой алгоритм". 1

@JamesBlack 46 / 46 / 5 Регистрация: 28.07.2009 Сообщений: 144
	07.05.2010, 23:26 [ТС]	3
	наконец-то, хоть какая-то зацепка! Спасиб! 0

Опции темы