[C] Ohodnoteny graf

Marcello123 · Napísal **Marcello123**: 13.12.2014 18:27

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

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

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

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

Ano presne tak

reDo · Napísal **reDo**: 14.12.2014 14:57

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

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

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

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

reDo · Napísal **reDo**: 14.12.2014 15:44

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

Podobné témy