Наидлиннейший путь в графе(ну или не самый короткий)

[Kaner]

Есть граф. Если из одной вершины можно попасть в другую,то в матрице смежности 1, если нельзя или же элемент [i][i] то 0.


Функция :

         public function maxWay2(d:Array,x:Number):Array{
 
                       //d-матрица смежности
                       //x-элемент который есть начало поиска замкнутого пути
 
			var i:int; //счетчик
			var j:int; //счетчик
			var l:int=-1; //счетчик
			var put:Array=new Array(); //туда будем добавлять номера элементов пути
			var end:Boolean=false; //переменная для проверки окончания поиска
 
 
			for(i=0;i<d.length;i++) //цикл по размерности матрицы смежности,т.е по кол-ву элементов в графе
			{
				if(d[x][i]==1) //если нашли связь с каким-то элементом то...
				{
					l++; //делаем l=0
					put[l]=i; //записываем этот элемент в путь
					i=d.length; //завершаем цикл по i
					j=-1; // делаем -1 чтобы инкриминировать в начале следующего цикла 
					while(end==false) 
					{
						j++;
 
						if(d[put[l]][j]==1 && provMas(put,j)==-1) //если находим элемент, с которым есть связь у предыдущего элемента добавленного в наш путь и он
                                                  // не содержится в пути то...
							{
								l++;							
								put[l]=j; //добавляем этот элемент в путь
								j=-1; //присваиваем -1 чтобы начать поиск уже для нового элемента
 
							}
							if(put[l]==x || j>=d.length) //критерии окончания поиска:если нашли замкнутый путь или если не нашли связь 
							{
								end=true;
							}
 
					}
				}
			}
 
			if(put[l]==x && l!=-1) //если получили замкнутый путь и вошли  в самый первый if то возвращаем путь
			{
				return put;
			}
			return[-1,-1];
 
		}
 
                public function provMas(a:Array,sE:Object):int {
			for(var i:int=0;i < a.length;i++)
			{
				if (a[i].toString()==sE.toString()) { 
					return i;
				}			
			}
			return -1;
		}

Она ищет неминимальный путь но не всегда максимальный.
как переделать функцию под максимальный путь?

[goodguy]

Очередная жесть. Кто писал эту функцию?
Где хоть один комментарий?
О каких путях идет речь?
Откуда в нее передаются данные?
Я сильно удивлюсь, если кто-то тут ответит на этот вопрос при таком раскладе.

[Kaner]

Добавил комментарии.
Функцию писал я.

О каких путях идет речь?

о замкнутых путях. В функцию я передаю х-это должно стать началом и концом замкнутого пути если он есть

[mikhailk]

Какая изначально задача решается?
Кстати, не знаю, что там за граф, но в графе с циклом длина максимального пути стремится к бесконечности.

[wvxvw]

Проблема с восприятием такого кода в том, что вы используете непонятные названия для переменных / очень неспецифические типы. Кроме того, есть вещи, которые, хоть и будут работать, их никто не делает, т.как они бессмысленны, например сравнивать булевые значения с переменными булевого типа - if (variable == true) - бессмысленное выражение, т.как достаточно было if (variable). Кроме того, существует традиция, согласно которой инфиксные опереаторы обрамляюстся пробелами с двух сторон, а префиксный или постфиксные - нет. Это значит, что -i или i++ нужно писать слитно, а i == j нужно писать раздельно. Это не ошибка, но заставляет читающего "спотыкаться".
К сожалению я недостаточно знаком с графами, чтобы что-то посоветовать по сути вопроса.

[-De-]

Это NP-полная задача. Т.е. перебор (что долго), либо эвристики или что-то подобное (что не гарантирует максимальности).

[Kaner]

Вобщем так: я пишу игру точки,думаю все знают,что это такое. И для обвода точек, мне и нужно находить этот наидлинейший путь/цикл.
Я пытался использовать разные методы для графов..не очень получается,по идее надо написать рекурсивную функцию.Кто-нибудь может помочь.Исходные данные для функции это матрица смежности.

[t4arty]

хм... можете посмотреть так называемый "жадный алгоритм" может он и сойдет.

[Котяра]

берём астар и ставим отрицательные веса.

[-De-]

Если те точки, в которые я играл, то нужна наибольшая площадь, а не путь.
Я бы сделал так: охватываем прямоугольником, который затем скукоживаем, пока не получим подходящую охваченную область (когда все точки периметра - наши - это она). Довольно муторно, но вроде реализуемо.
Или (по идее легче) - берём самую верхнюю точку и обходим из неё область по часовой стрелке. Если по завершению обхода отбросить висячие концы, то должно выйти типа того, что надо. Если не выходит, то выкидываем из рассмотрения пройденные точки и назначаем новую верхнюю точку.