Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C] Algorytm Dijkstry, najkrótsza droga w grafie.

huzio123 07 Cze 2011 22:01 6982 7
  • #1 07 Cze 2011 22:01
    huzio123
    Poziom 9  

    Mam do napisania program oparty na algorytmie Dijkstry, czyli wyszukiwanie najkrótszej drogi w grafie. I tu zaczyna się problem bo nie mogę znaleźć dokładniejszych informacji w internecie jak ten algorytm wygląda i jak go zaimplementować. Wszelaka pomoc mile widziana.

    0 7
  • #3 07 Cze 2011 22:27
    huzio123
    Poziom 9  

    Patrzyłem na te linki ale nie wiem dokładnie i tak o co w tym chodzi, nie miałem grafów na zajęciach i ciężko mi to zrozumieć. Widziałem że tam jest gotowiec ale co mi po nim jak się tego nie nauczę

    1
  • #4 07 Cze 2011 23:14
    kuba1im
    Poziom 19  

    Ale co tutaj jest do rozumienia czego nie ma w pierwszym linku? Jest graf czyli połączenie ścieżek i wierzchołków, którymi programowo mogą być obiekty jakieś klasy przechowujące np. jakąś wartość i wskaźniki do innych obiektów. Te wskaźniki to właśnie ścieżki (przejścia/połączenia itp), mogą mieć różne wagi, ale nie muszą. Algorytm Dijkstry wyznacza najkrótszą ścieżkę z wierzchołka A do wierzchołka B, a jak? To już jest opisane w pierwszym linku. Jak już się w niego zagłębisz to w drugim jest przykład, na którym możesz się oprzeć (a nie przepisać jako gotowiec) pisząc swój własny program.

    0
  • #5 08 Cze 2011 01:26
    lolcio
    Poziom 16  

    Spróbuj cos napisać a jak nie będzie działać to Ci pomożemy...ten algorytm jest dość kapryśny ale poczytaj i spróbuj napisać :P

    0
  • #6 22 Cze 2011 07:55
    huzio123
    Poziom 9  

    Ok, tyle udało mi się napisać:

    Kod: c
    Zaloguj się, aby zobaczyć kod

    I mam problem, wszystkie procedury jakie znalazłem do deklaracji wskaźnika nie pasują, zawsze jest ten sam błąd. Reszta wskaźników wydaje mi się dobrze bo wzorowałem się na gotowych rozwiązaniach z internetu.

    0
  • Pomocny post
    #8 26 Cze 2011 18:58
    bzyku_bd
    Poziom 12  

    Witam.
    Robiłem taki algorytm na projekt w tym roku, także wrzucam (wprawdzie jest cpp, ale większość cpp to cin i cout, reszta na wskaznikach takze latwo przerobic na c).
    Program przyjmuje graf w takiej formie (w pliku tekstowym):

    0 2 3
    2 0 4
    3 4 0

    Czyli po prostu macierz sąsiedztwa.
    Pozdrawiam

    1
    Załączniki: