Najkratšia cesta s podmienkami – Java – Fórum – Programujte.com

Zdravím,

poterbujem nájsť najkratšiu cestu v grafe medzi rôznymi dvojicami vrcholov.

Problém je v tom, že dĺžky hrán, cez ktoré vedie cesta musia rásť a cesta musí prechádzať cez najviac x hrán.

To znamená, že najkratšia cesta, ktorá spĺňa prvú podmienku nemusí spĺňať druhú a preto nie je vhodná.

Graf je orientovaný a ohodnotený, ale medzi niektorými vrcholmi môže ísť viac hrán s rôznou dĺžkou (v rovnakom smere).

Na riešenie úvodného problému by som asi použil Floyd-Warshallov algoritmus, ale ako ho modifikovať tak, aby boli splnené? Tiež mám trochu problém s tými viacerými hranami.

//Floyd-Warshall
for (int k=0; k<n; k++) {
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			int a=vz[i][k]+vz[k][j];
			if (a<vz[i][j]) vz[i][j]=a;
		}
	}
}

Nejaké nápady ako začať?

Ďakujem za odpoveď

'dĺžky hrán, cez ktoré vedie cesta musia rásť'
Jestli je to chapano tak, ze vzdalenost mezi body musi narustat, 1 + 2 + 3, tak nasledujici vzdalenost musi byt vetsi nez predchozi, jednoducha podminka. Ulozis si predchozi hodnotu treba do tmp a porovnas v dalsim kroku s tmp. Nebo, pokud do pole s cestou ukladas i vzdalenost, tak to vytahnes z pole 

if (cesta[i-1]['vzdalenost'] < nova_trasa['vzdalenost']) {...}

'cesta musí prechádzať cez najviac x hrán'
Kdyz uz mas treba delku cesty 6 bodu a sesty bod neni konecny bod B, tak cyklus prerusis break (continue) s tim, ze nejakym booleanem budes rikat, ze cesta neni platna.
Preruseni cyklu je break, prejit k dalsi hodnote je continue.

#2 peter
Áno, vzdialenosť medzi vrcholmi, cez ktoré prechádzame musí narastať.

Je použitie Floyd-Warshalla vhodné?

 Skúsil som to ako si hovoril, uložiť si predchádzajúcu vzdialenosť do tvz ale nefunguje to.

for (int k=0; k<n; k++) {
	for (int i=0; i<n; i++) {
		int tvz=0;
		for (int j=0; j<n; j++) {
			int a=vz[i][k]+vz[k][j];
			if (a<vz[i][j] && vz[k][j]>tvz) { 
				vz[i][j]=a;
				tvz=vz[k][j];
				ph[i][j]++;
			}
		}
	}
}

Napr. pre takýto graf:

Připojen obrázek.

je cesta z bodu 1 do 4 cez najviac 2 hrany dlhá 14, cez max. 3 je dlhá 15. Cesta z bodu 2 do 5 nanajviac 5 hrán neexistuje.

Porovnáváš délku dvou cest místo dvou kroků jedné cesty. A určení maxima znamená hodnoty menší nebo rovné maximu.

Se na to divas moc vedecky, asi. Vem si par kolicku, zapichej do zeme, zmer vzdalenosti a zkus si na papir napsat vsechna mozna reseni, podle obrazku. Pritom vetsinou prijdes na postup, ktery jsi pouzival. Podle toho pak napis program.
Vymyslet jen tak bez rozmysleni slozitejsi kod vetsinou konci nezdarem, neco zapomenes, prehlednes.