Zdravim, mam spravit projekt na sietovu analyzu. Ma to byt desktopovy program s grafickym rozhranim, kde zadame lubovolny graf s najdlhsou cestou zaciatocneho bodu do koncoveho (4-9 vrchovol, 5-15 hran), ulohou je dopocitat ostatne hrany tak, aby zadana cesta bola stale najdlhsia

Pre ilustraciu pripajam obrazok, ako by mal vyzerat vstup, v tomto pripade mame najdlhsiu cestu cez body 1-3-4-6-7-9 s dlzkou 25, teda uloha je dopocitat ocenenia ostatnych hran, tak aby bola zachovana dana najdlhsia cesta. Vedeli by ste poradit akym sposobom robit algorytmus na dopocitanie tychto hran?

Mne napadlo, ze z grafickeho rozhrania si program vezme vstupy
- pocet hran, pocet vrcholov
- data z ktoreho vrcholu sa mozem dostat kam

Program by dalej vygeneroval vsetky mozne cesty s tym, ze by zo vstupu uz poznal najdhsiu z nich a potom podla toho dopocital ostatne cesty tak aby nemali vyssie ocenenie.

Tu som sa uz zasekol, neviem ako to zrealizovat pomocou algorytmu, mate nejake rady ako dalej? dakujem

PS....planujem to robit v Jave

Môže graf obsahovať cykly a viacnásobne hrany, môžu byt hrany ohodnotené reálnymi číslami, môžu mat záporné hodnoty ?

Len tak pre zaujimavost kde studujes ?

Ma to byt orientovana acyklicka siet, studujem EUBA-FHI

Ak som to spravne pochopil v naivnom algorytme by ti stacilo dat vsetkym hranam hodnotu 1.

No v tom "lepsom" by som to riesil asi takto:
1, ohodnotis si vrcholi ( vzdialenost od zaciatku )
2, rekurzivnym zostupom pocitas neohodnotene vrcholi pre vsetky cesty ( ak narazis na ohodnoteny vrchol zacnes s pocitanim odznovu)
a pri navrate z ich ohodnocovat podla cisel
3,dopocitas hodnoty hran

Toto je len priblizny napad ako to riesit skus ho nejak rozumne rozvyt.

Na tvojom sposobe mi trochu vadi pocitanie hodnoty vrcholov, pretoze vo vyslednom grafe sa do urciteho vrchlu mozes dostat rôznou cestou s inym ohodnotenim.

Dnes mi napadol sposob, prehladavanim do sirky najst vsetky mozne cesty zo zaciatku do konca a podla najdlhsej cesty (zadanej pri vstupe) dopocitavat hrany tak aby ziadna cesta nebola dlhsia ako ta zadana.

V mojom algoritme je hodnota vrcholu maximum zo vsetkych moznych ( respektyve prva hodnota, co by malo byt to iste).

Aj tvoje riesenie je mozno dobre, byt tebu zacnem prototypovat ( sam tak vyvjam softver ) a oskusat si napady.
Prosto si spravis co najjednoduchsiu aplikaciu ( nemusi byt ani v jave ) a tam si odkusas princip.