Ścieżka w grafie o jak największej sumie wag z dodatkowym warunkiem.

A więc mam taki problem. Mam wyznaczyć "najtrudniejszą" ścieżkę z jednego punktu do drugiego, pod warunkiem, że wartość w każdym następnym punkcie, zawsze będzie większa lub równa poprzedniej wartości w punkcie.

Wagi między punktami to (mapa[x][y]-mapa[a][b])^2, gdzie x,y to wsp. punktu bieżącego, a a,b to wsp. punktu następnego.

Do wyznaczenia najtrudniejszej ścieżki w grafie użyłem algorytmu Dijkstry (lecz z odwróconym warunkiem dotyczących wag) i zwykłego warunku w if'ie (jeżeli następna wartość jest większa bądź równa aktualnej to jest ok). Niestety nie jest to dobre rozwiązanie i algorytm nie wynajduje najtrudniejszej ścieżki.

Przykładowy zestaw danych i 2 ścieżki: ( 2-liniowa jest poprawna, a 1-liniowa to ta którą generuje mój algorytm)** 8-start, 40-koniec**

Gdzie tkwi problem ? Dodam, że ten sam algorytm Dijkstry z normalnym warunkiem dotyczącym wag działa i bez problemu odnajduje najkrótszą ścieżkę w grafie (ścieżkę o najmniejszej sumie wag).

Dziękuję z góry za każdą pomoc :)

Co to jest najdłuższa ścieżka niby? Bo na pewno nie to co na obrazku. Nie chodzi aby czasem jednak o najkrótszą ścieżkę o największej sumie wag krawędzi, przy zachowaniu warunku że możemy iść tylko przez węzły o coraz wyższych wagach?

Masz rację, źle napisałem. Chodzi o znalezienie "jak najtrudniejszej" ścieżki. Nie musi być krótka, tylko mieć jak największą sumę wag przy spełnieniu założenia, że wartość w każdym następnym punkcie jest >= od wartości w punkcie poprzednim.

Link do treści zadania. Może tam jest jaśniej opisane ;)
http://prntscr.com/dwtwdh

Tak na oko to poprawnie zaimplementowany Dijkstra powinien ten problem rozwiązywać. Na pewno sie nie pomyliłeś gdzieś?

Szczerze mówiąc to nie sądze, bo dla danych 5x5,10x10,15x15,20x20, a nawet 1000x1000 Dijkstra liczy poprawnie.

Wklejam kod na najtrudniejszą drogę. Jakbyś miał czas zerknąć, to będę bardzo wdzięczny :) Jest to Dijkstra z Priority Queue:

Klasa Dijkstra to tylko współrzędne punktu i koszt dotarcia do niego. Point wiadomo x,y.

private static void hard_way ()
	{

		class DijkstraMax implements Comparator<Dijkstra> {


			@Override
			public int compare(Dijkstra d1, Dijkstra d2) {

				if(d1.d < d2.d)
				{
					return 1;
				}
				else if(d1.d == d2.d)
				{
					return 0;
				}
				else
				{
					return -1;
				}

			}
		}

		int d[] = new int[map.length*map[0].length];	//minimalny koszt dojscia
		Point p[] = new Point[map.length*map[0].length];	//poprzednik


		int hardLvl;
		String hDirections;

		ArrayList<Point> Q = new ArrayList<>();		//tab wszystkich wierzcholkow 1d

		Comparator<Dijkstra> comparator = new DijkstraMax();
		PriorityQueue<Dijkstra> queue = new PriorityQueue<>(map.length*map[0].length, comparator);

		for(int i=0;i<map.length*map[0].length;i++)
		{
			p[i] = new Point(-1,-1);
			d[i] = Integer.MIN_VALUE;
			dCheck[i] = false;
		}

		for(int i=0;i<map.length;i++)
		{
			for(int j=0;j<map[0].length;j++)
			{
				Q.add(new Point(i,j));
			}
		}

		queue.add(new Dijkstra(new Point(start.x,start.y), 0));

		Dijkstra dij;

		while(!queue.isEmpty())
		{

			dij = queue.poll();


			int x = dij.u.x;
			int y = dij.u.y;

			dCheck[x*map.length+y] = true;

			for(int a = x - 1; a <= x + 1; a++)
			{
				for (int b = y - 1; b <= y + 1; b++)
				{
					if (x == a && y == b)
					{
						b++;
					}

					if (a >= 0 && b >= 0 && a < map.length && b < map[0].length)
					{

						if(d[a*map.length+b] == Integer.MIN_VALUE && !dCheck[a*map.length+b] && map[x][y] <= map[a][b])
						{
							d[a*map.length+b] = d[x*map.length+y] + (int) Math.pow(map[x][y] - map[a][b], 2);
							p[a*map.length+b] = dij.u;
							queue.add(new Dijkstra(new Point(a,b), d[a*map.length+b]));
						}
						else if(!dCheck[a*map.length+b] && d[a*map.length+b] < d[x*map.length+y] + (int) Math.pow(map[x][y] - map[a][b], 2) && map[x][y] <= map[a][b])
						{
							d[a*map.length+b] = d[x*map.length+y] + (int) Math.pow(map[x][y] - map[a][b], 2);
							p[a*map.length+b] = dij.u;
							queue.add(new Dijkstra(new Point(a,b), d[a*map.length+b]));
						}

					}
				}
			}





		}

		findWayBack(Q, p, hArray);

		hardLvl = calcHardness(hArray);

		System.out.println("\nTrudnosc trudnej drogi: "+hardLvl);

		hDirections = determineDirections(hArray);

		System.out.println("Kierunki trudnej drogi: "+hDirections);

	}

	private static void findWayBack(ArrayList<Point> Q, Point p[], ArrayList<Point> array)
	{
		int index = end.x*map.length+end.y;
		Point wsk = Q.get(index);
		array.add(wsk);

		while(wsk.x != start.x || wsk.y != start.y)
		{
			array.add(p[index]);
			wsk = p[index];

			for(int i=0;i<Q.size();i++)
			{
				if(p[index].x == Q.get(i).x && p[index].y == Q.get(i).y)
				{
					index = i;
					break;
				}
			}
		}

	}

	private static int calcHardness(ArrayList<Point> s)
	{
		int var=0;

		for (int i=0;i<s.size()-1;i++)
		{
			var = (int) (var + Math.pow((map[s.get(i).x][s.get(i).y] - map[s.get(i+1).x][s.get(i+1).y]) ,2));
		}

		return var;
	}