[C] Ohodnoteny graf

Marcello123 · Napísal **Marcello123**: 13.12.2014 18:27 | [C] Ohodnoteny graf

Zdravím vedeľ by mi niekto pomôcť, ako vytvoriť ohodnotený orientovaný graf v C? Niečo mám napísané ale potreboval by som aby každý vrchol mal svoju váhu a aj funkciu (čo predstavuje)
Mám niečo takéto

Kód:

struct Hrana
{
    int from, to;    // vrcholy od, do
    int length;      // dlzka
};

struct Graf
{
    int n;           // pocet vrcholov
    
    struct Hrana *a; // hrany
    int m;           // pocet hran
};

struct Graf *create(int n, int m)
{
    struct Graf *g = (struct Graf *)malloc(sizeof(struct Graf));
    g->n = n;
    g->m = m;
    g->a = (struct Hrana *)malloc(m * sizeof(struct Hrana));
    return g;
}

reDo · Napísal **reDo**: 14.12.2014 9:20 | [C] Ohodnoteny graf

Coho graf chces vytvorit? Ak chces vahy vrcholov tak si urob dalsie pole, kde budu vahy pre jednotlive vrcholy. Alebo si urob strukturu PopisVrchola kde bude vaha a popis funkcie daneho vrchola a urobis si zase pole.

Marcello123 · Napísal autor témy **Marcello123**: 14.12.2014 13:24 | [C] Ohodnoteny graf

Dostanem takýto vstup

Kód:

6
1 100 1 4 10
1 50 1 5 20
2 200 2 4 40 5 40
2 50 1 4 5
0 20 4 5 10 0 20 2 10 3 10
0 30 3 1 30 2 20 4 20

kde prve cislo je pocet vrcholov a potom v kazdom riadku je cislo vrcholu, funkcia vrcholu, váha vrcholu, počet hrán, s akým vrcholom je spojený a aká je hodnota hrany.
a potom za použitia dijskrovho algoritmu musím nájsť najkratšiu cestu z funkcie 1 do funkcie 2

reDo · Napísal **reDo**: 14.12.2014 13:32 | [C] Ohodnoteny graf

Cize musis najst najkratsiu cestu z lubovolneho vrcholu, ktoreho funkcia je 1 do ineho lubovolneho vrcholu, ktoreho funkcia je 2?

Marcello123 · Napísal autor témy **Marcello123**: 14.12.2014 13:43 | [C] Ohodnoteny graf

Ano presne tak

reDo · Napísal **reDo**: 14.12.2014 14:57 | [C] Ohodnoteny graf

V tom pripade by bol lepsi Floyd Warshallov algoritmus, ktory najde najkratsie cesty z kazdeho vrcholu do kazdeho ineho. Jeho vyhoda je tiez, ze je velmi lahky na implementaciu. Zalezi, ale aky velky je vstup, pretoze casova narocnost tohto algoritmu je O( (pocet vrcholov) ^ 3 ). Tiez potrebujes maticu susednosti, lebo on pracuje s nou cize pamatova zlozitost bude O( (pocet vrcholov) ^ 2 ). Potom ako prejde tento algoritmus uz len prejdes tabulku a najdes dvojicu, ktora sa bude skladat z vrcholu s 1 a druhy s 2 a najkratsou dlzkou.

Marcello123 · Napísal autor témy **Marcello123**: 14.12.2014 15:10 | [C] Ohodnoteny graf

No ja potrebujem počítať s najhoršou časovou náročnosťou O(počet hrán * log(počet vrcholov)) preto tam musím použiť dijkstru

reDo · Napísal **reDo**: 14.12.2014 15:28 | [C] Ohodnoteny graf

Tak a kde je problem? Na nete je kopa kodov Dijkstra algoritmu resp co nevies urobit?

Marcello123 · Napísal autor témy **Marcello123**: 14.12.2014 15:30 | [C] Ohodnoteny graf

No neviem napisat spravne ten graf a potom ze co vseetko budem hladat s dijkstrom

reDo · Napísal **reDo**: 14.12.2014 15:44 | [C] Ohodnoteny graf

Nacitas si graf a potom vykonas dijkstru, pozri si nejake vysvetlenia na nete napr tu je pekne http://www.algoritmy.net/article/5108/D ... algoritmus. Na nete je kopa hotovych kodov kde sa mozes inspirovat.

[C] Ohodnoteny graf

[C] Ohodnoteny graf

Podobné témy

Vymena graf karty za novu graf kartu

Mám sa učiť C ++/objective C/ C#?

Hladam hracov na C&C Generals Zero Hour

Naučte se C++ za 21 dní + C++Builder 6

rozdiel medzi Borland 3.1 C++ vs Net. C++

K: PC Literaturu- C++/C#/java/python/ruby/RoR

Hledá se programátor C/C++ pro vesmírné projekty (Praha)

Čo mi treba na programovanie v C/C++

aky je rozdiel medzi C++ a Visual C++ ?

Darujem knihy o programovaní (HTML, Java, Visual C++, C++ Builder, Android)

Hladame 3x C/C++ Linux developer- projekt 11/2016-2/2017

C - Ako prekompilovať .c súbor do .exe?

C/C++ problém so súbormi a hodnotami

program na projekt (C#, C++, pascal, java)

C# alebo C++ , ktore knizky na ucenie?

Ako nastavit grafikuv AMD catalyst c.c.