Najkratšia cesta s podmienkami – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Jozef010
Newbie
22. 11. 2017   #1
-
0
-

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ď

Nahlásit jako SPAM
IP: 212.26.187.–
peter
~ Anonymní uživatel
4014 příspěvků
23. 11. 2017   #2
-
0
-

'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.

Nahlásit jako SPAM
IP: 2001:718:2601:258:b01b:ab...–
Jozef010
Newbie
24. 11. 2017   #3
-
0
-

#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.

Nahlásit jako SPAM
IP: 212.26.187.–
gna
~ Anonymní uživatel
1891 příspěvků
24. 11. 2017   #4
-
0
-

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

Nahlásit jako SPAM
IP: 213.211.51.–
peter
~ Anonymní uživatel
4014 příspěvků
25. 11. 2017   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 193.84.205.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 41 hostů

Podobná vlákna

Relativní cesta — založil Radmill

Cesta k souborům — založil Jiri

Cesta k Po spuštění — založil Midnight

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý