Egy nagyobb túrát tervezünk. A térkép egy gráffal adott, amiben a csúcsok az útelágazások, az élek a közöttük vezető utak, mindegyikhez élsúlyként meg van adva, hogy mennyi idő alatt tudjuk megtenni azt az útszakaszt. Továbbá a gráf minden csúcsához adott egy szám, hogy a neki megfelelő helynek mennyi a tengerszint feletti magassága. Azt akarjuk meghatározni, hogy ha adottak az A, B csúcsok és a T, M számok, akkor el lehet-e jutni A-ból B-be úgy, hogy hogy T időn belül megérkezzünk, és közben érintsünk egy legalább M magasságú pontot is.
Melyik ad ennek meghatározására hatékony módszert?

Question

Egy nagyobb túrát tervezünk. A térkép egy gráffal adott, amiben a csúcsok az útelágazások, az élek a közöttük vezető utak, mindegyikhez élsúlyként meg van adva, hogy mennyi idő alatt tudjuk megtenni azt az útszakaszt. Továbbá a gráf minden csúcsához adott egy szám, hogy a neki megfelelő helynek mennyi a tengerszint feletti magassága. Azt akarjuk meghatározni, hogy ha adottak az A, B csúcsok és a T, M számok, akkor el lehet-e jutni A-ból B-be úgy, hogy hogy T időn belül megérkezzünk, és közben érintsünk egy legalább M magasságú pontot is.

Melyik ad ennek meghatározására hatékony módszert?

Answer

A gráfból elhagyjuk az  M -nél alacsonyabban levő pontokat, kivéve  A  és  B . Ebben a gráfban keresünk Dijkstra algoritmusával legrövidebb utat  A -ból  B -be.

Answer

A többi állítás egyike sem  helyes.

Answer

Az élsúlyozott gráfon Dijkstra algoritmusával meghatározzuk, hogy hova juthatunk el  A -ból  T  időn belül. Ha ebben  benne van  B , akkor igen, különben nem.

Answer

Az élsúlyozott gráfon Dijkstra algoritmusával meghatározzuk, hogy hova juthatunk el  A -ból  T  időn belül. Ha ebben benne van  B  és van  M  magas pont is, akkor igen, különben nem.

Answer

Az élsúlyozott gráfon  Dijkstra algoritmusával meghatározzuk a legrövidebb utat  A -ból  B -be, és ha ez tartalmaz egy legalább  M  magasságú pontot, akkor igen, különben nem.

Crowdly

Egy nagyobb túrát tervezünk. A térkép egy gráffal adott, amiben a csúcsok az úte...

Want instant access to all verified answers on edu.vik.bme.hu?