2021-05-06.md

tags	vaje, or, grafi
hackmd	https://hackmd.io/5jOwGfzfR5yZnm8uwWz0_w
plugins	mathjax

Operacijske raziskave - vaje 6.5.2021

---

Iskanje v širino

class Graf:
    ...
    
    def BFS(G, koreni=None, visit=None):
        if koreni is None:
            koreni = G.vozlisca()
        if visit is None:
            def vist(u, v):
                pass
        globina = {}
        stars = {}
        for w in koreni:
            if w in globina:
                continue
            nivo = [w]
            globina[w] = 0
            stars[w] = None
            i = 1
            while len(nivo) > 0:
                naslednji = []
                for u in nivo:
                    visit(u, stars[u])
                    for v in G.sosedi(u):
                        if v not in globina:
                            globina[v] = i
                            stars[v] = u
                            naslednji.append(v)
                nivo = naslednji
                i += 1
        for u in G.vozlisca():
            if u not in globina:
                globina[u] = float('inf')
                stars[u] = None
        return (globina, stars)

Časovna zahtevnost: $O(m) + O(n)$ klicev funkcije visit

---

Naloga 1

Na sledečem grafu izvedi iskanje v širino. V primerih, ko imaš več enakovrednih izbir, upoštevaj abecedni vrstni red. Za vsako povezavo določi, ali se nahaja v drevesu iskanja v širino.

---

---

Naloga 2

Zapiši algoritem, ki za vhodni graf $G$ določi njegov premer.

---

class Graf:
    ...
    
    def premer(G):
         max(x for u in G.vozlisca()
               for x in G.BFS(koreni=[u])[0].values())

Časovna zahtevnost: $O(mn)$

---

Dijkstrov algoritem

class UtezenDigraf(Digraf):
    ...
    
    def utezeniSosedi(G, u):
        """
        Vrne slovar uteži povezav
        od u do vsakega njegovega izhodnega soseda.
        """
        ...
        
    def dijkstra(G, koren):
        Q = PrednostnaVrsta({v: 0 if v == koren
                                else float('inf')
                             for v in G.vozlisca()})
        razdalja = {}
        stars = {koren: None}
        while len(Q) > 0:
            v, d = Q.pop() # vozlišče z najmanjšo razdaljo odstranimo iz vrste
            razdalja[v] = d
            for w, t in G.utezeniSosedi(v).items():
                if w in razdalje:
                    continue
                r = d + t
                if r < Q[w]:
                    Q[w] = r
                    stars[w] = v
        return (razdalja, stars)

Časovna zahtevnost:

• s slovarjem: $O(n^2)$
• s kopico: $O(m \log n)$

---

Naloga 3

S pomočjo Dijkstrovega algoritma določi razdalje od vozlišča $A$ do ostalih vozlišč.

---

---

Naloga 4

Naj bo $G = (V, E)$ graf, za katerega so dolžine povezav določene s funkcijo $\ell : E \to \mathbb{R}$ (tj., dolžine so lahko tudi negativne). Definirajmo še funkcijo $\ell' : E \to \mathbb{R}$ tako, da velja $\ell'(e) = \ell(e) - \min{\ell(f) \mid f \in E}$ (dolžine, določene z $\ell'$, so torej nenegativne).

Dokaži ali ovrzi: drevo najkrajših poti, ki ga Dijkstrov algoritem ustvari ob vhodu $(G, \ell')$, je tudi drevo najkrajših poti za graf $G$ z dolžinami povezav, določenimi z $\ell$.

---

---

Naloga 5

Denimo, da imamo neusmerjen graf $G = (V, E)$, katerega vozlišča predstavljajo mesta, povezave pa predstavljajo ceste, ki jih povezujejo. Za vsako povezavo $e \in E$ poznamo njeno dolžino ${\ell_e}$ (v kilometrih).

Priti želimo iz mesta $s$ v mesto $t$. V vsakem mestu je bencinska črpalka, ob cestah pa teh ni. Žal imamo na voljo samo star avto, ki lahko s polnim rezervoarjem prepelje le $L$ kilometrov.

1. Zapiši algoritem, ki v linearnem času poišče pot, ki jo lahko prevozimo z našim avtom, oziroma ugotovi, da ta ne obstaja.

2. Izkaže se, da z našim avtom te poti ne moremo prevoziti, zato se odločimo za nakup novega. Zapiši algoritem, ki v času $O(m \log n)$ določi najmanjše število prevoženih kilometrov, ki naj jih avto zmore z enim polnjenjem, da bo pot od $s$ do $t$ mogoča.

---

Naloga 6

Zasnuj različico Dijkstrovega algoritma za iskanje najkrajše poti med vozliščema $s$ in $t$ v grafu $G$, ki iskanje hkrati začne v vozliščih $s$ in $t$. Kdaj naj se iskanje konča in kako naj se poišče rešitev?