Rešitev: Dijkstrov algoritem (Mathematica)

Iz MaFiRaWiki

Naloga: Dijkstrov algoritem

Vsebina

Kaj je Dijkstrov algoritem?


Dijkstrov algoritem ali drevo najkrajših poti se uporablja za iskanje vpetega drevesa, ki vsebuje vse najkrajše
poti iz vozlišča v do vseh ostalih vozlišč v drevesu. Razvil ga je nizozemski računalniški znastvenik Edsgar
Wybe Dijkstra (1930-2002) in sicer s pomočjo požrešne metode.


Osnovna ideja Dijkstrovega algoritma?


Pri Dijkstrovem algoritmu gradimo drevo na vsakem koraku posebej. Na začetku se v našem povezanem delu nahaja
le vozlišče v (zanimajo nas najkrajše poti od v pa do vseh ostalih vozlišč), v nepovezanem pa je vse ostalo
(d(v, x_i=∞, izjema so sosednja vozlišča). Nato pa pogledamo katera povezava iz v do njenih sosedov je za nas
najbolj ugodna (t.j najcenejša) recimo, da je to povezava od v do x_1 in jo dodamo v povezan del (d(v,x_1)≠∞ 
in manjša od vseh d(v,x_sosedov)). Sedaj gledamo povezave iz v in x_1, ki so v nepovezanem delu in spet ocenimo 
katera povezava je za nas najbolj ugodna...s tem postopkom nadaljujemo dokler ne dobimo vseh vozlišč v naš povezan 
del (pri tem pazimo da ne dobimo ciklov).

Dijkstrov algoritem v mathematici


Clear[DijkstrovAlgoritem]

DijkstrovAlgoritem::usage ="Funkcija DijkstrovAlgoritem[g,v] uporabi Dijkstrov algoritem za iskanje 
najkrajše poti iz vozlišča v do vseh ostalih vozlišč v grafu g (graf g je podan z matriko uteži). 
Funkcija nam vrne seznama p in d. p[[i]] je neposredni prednik od vozlišča i in d[[i]] je cena, ki je 
potrebna, da pridemo od vozlišča v do vozlišča i (ta cena je seveda najmanjša možna).

OPOMBA: Deluje tako za usmerjene in kot tudi za neusmerjene grafe.";

DijkstrovAlgoritem[g_List, v_Integer] := Module[{n, p, d, P, N, x, m, i, u},
    n = Length[g];
    P = {v};                                                        (*P je povezani del*)
    N = DeleteCases[Range[n], v];       (*N je nepovezani del*)
    p = Table[v, {n}];                                 (*p je seznam prednikov*)
    d = Table[g[[v, i]], {i, n}];          (*d je seznam najmanjših cen do povezanega dela*)
    p = ReplacePart[p, "-", 1];
    d = ReplacePart[d, 0, 1];
    While[Length[N] > 0,
      x = v;
      m = ∞;                                                         (*umeten pogoj*)
      For[i = 1, i ≤ Length[N], i++,    
        (*izmed vseh vozlišč v nepovezanem delu izberemo tistega, z najmanjšo ceno do povezanega dela (d)*)

        u = N[[i]];
        If[d[[u]] < m, x = u; m = d[[u]]]
        ];
        P = Append[P, x];                                  (*to vozlišče damo v P in odstranimo iz N*)
        N = DeleteCases[N, x];
      (*Za vsako vozlišče v "novonastalem" N preverimo ali je prejšnja cena do povezanega dela večja od trenutne 
      (po dodanem vozlišču x). Če je , jo zamenjamo s trenutno.*)

      For[i = 1, i ≤ Length[N], i++,
        u = N[[i]];
        If[d[[u]] > g[[x, u]] + d[[x]], d[[u]] = g[[x, u]] + d[[x]]; p[[u]] = x]
        ]
      ];
    Return[{p, d}]
    ]

Primer

1.primer je za neusmerjen graf:

Clear[DikstrovAlgoritem,g1]

g1 = {{∞, 4, ∞, ∞, 2}, {4, ∞, 11, ∞, ∞}, {∞, 11, ∞, 7, ∞}, {∞, ∞, 7, ∞, 5}, {2, ∞, ∞, 5, ∞}};  
DijkstrovAlgoritem[g1, 1]

rešitev: {{-, 1, 4, 5, 1}, {0, 4, 14, 7, 2}}

2.primer je za usmerjen graf:

Clear[DijkstrovAlgoritem,g2]

g2 = {{∞, 10, 5, ∞, ∞}, {∞, ∞, 2, 1, ∞}, {∞, 3, ∞, 9, 2}, {∞, ∞, ∞, ∞, 4}, {7, ∞, ∞, 6, ∞}};
DijkstrovAlgoritem[g2, 1]

rešitev:{{-, 3, 1, 2, 3}, {0, 8, 5, 9, 7}}
 

Zgled z grafom

Na spodnjem grafu bomo uporabili Dijkstrov algoritem:

V 1.koraku se odločimo do katerega vozlišča nas zanimajo najkrajše poti...npr: a (sosednji vozlišči sta na razdalji 1 in 10 od a, vsa ostala pa na razdalji ∞, saj ni še nobenih povezav med njimi v povezanem delu). Pogledamo kateri so njeni sosedi in izberemo povezavo, ki je najcenejša...v našem primeru je to povezava od a do e ter jo dodamo v naš povezan del:

Sedaj, ko je e v povezanem delu, razdalja od d do a ni več ∞ temveč 3 (1+2).

V naslednjem koraku pogledamo vse povezave iz a in e, ki so v nepovezanem delu (povezava od a do b , povezava od e do d) in izberemo najugodnejšo...to je povezava od e do d:

Sedaj ko je d v povezanem delu, se spremeni razdaljo od c do a in sicer je 11 (3+9) ter tudi(!) od b do a, saj je razdalja od b do a cenejša preko d in e (je 8 (=3+5)) kot direktno od a do b.

Ponovimo postopek in vidimo da ja naša najboljša možnost od d do b (lahko jo vzamemo, saj ne dobimo cikla):

S tem ko smo dodali c, se preko c ne pojavi nobena cenejša možnost, zato moramo izbrati samo še zadnjo povezavo, tako da bodo vsa vozlišča v povezanem delu in to storimo analogno...


Osebna orodja