Grafové problémy

Note	Ohodnocené grafy, definice nejkratší cesty, minimální kostry grafu, algoritmy pro hledání nejkratších cest (Dijkstrův, Bellman-Fordův algoritmus) a minimálních koster v grafu. IB000, IB002

Vážený (ohodnocený) graf

Je graf $G$ spolu s ohodnocením hran reálnými čísly $w : E (G) \to R$ .

Váha podgrafu $H$ je součet vah na hranách $H$ :

d_{G}^{w} (H) = e \in E (P) \sum w (e)

Nejkratší cesta

V neohodnoceném grafu je délka nejkratší cesty z $s$ do $t$ minimální počet hran na cestě z $s$ do $t$ . Značíme $δ (s, t)$ . Neexistuje-li cesta, pak $δ (s, t) = \infty$ .

Ve váženém grafu je délka nejkratší cesty dána:

δ (s, t) = {min {d_{G}^{w} (P) ∣ P je cesta z s do t} \infty kdy \overset{z}{ˇ} s ⇝ t jinak

Nejkratší cesta je pak každá cesta, která má délku nejkratší cesty.

Další pojmy nejkratších cest

Relaxace hrany $(u, v)$: Zkrácení vzdálenosti k vrcholu $v$ průchodem přes vrchol $u$ . Musí platit $u .distance + w (u, v) < v .distance$ . Hrana $(u, v)$ je v takovém případě napjatá.

Průzkum do šířky

Na neohodnocených grafech dává nejkratší cestu z počatečního vrcholu do všech ostatních.

Bellman-Fordův algoritmus

Hledá nejkratší cestu z daného vrcholu do všech ostatních. Funguje i v grafech se zápornými hranami. Pokud najde cyklus záporné délky, vrátí false.

Má složitost $O (V \cdot E)$ .

def bellmanford(graph: List[List[Tuple[int, int]]], s: int) \
        -> Tuple[bool, List[int], List[int]]:
    # graph is an adjacency list of tuples (dst, weight)
    distance = [float('inf') for i in range(0, len(graph))]
    distance[s] = 0
    parent = [-1 for i in range(0, len(graph))]

    for _ in range(1, len(graph)):
        for u in range(0, len(graph)):
            for edge in graph[u]:
                (v, w) = edge
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w
                    parent[v] = u

    for u in range(0, len(graph)):
        for edge in graph[u]:
            (v, w) = edge
            if distance[u] + w < distance[v]:
                return (False, None, None)
    return (True, distance, parent)

Dijkstrův algoritmus

Varianta BFS s prioritní frontou. Funguje na na grafech s nezáporným ohodnocením hran.

Složitost závisí na implementaci prioritní fronty. Je to $Θ (V)$ insertů, $Θ (V)$ hledání nejmenšího prvku, $Θ (E)$ snížení priority.

Implementace níže používá pole (resp. Pythoní list), tedy složitost je $Θ (V^{2})$ , jelikož hledání minima je lineární.

def dijkstra(graph: List[List[Tuple[int, int]]], s: int) \
        -> Tuple[List[int], List[int]]:
    # graph is an adjacency list of tuples (dst, weight)
    distance = [float('inf') for i in range(0, len(graph))]
    distance[s] = 0
    parent = [-1 for i in range(0, len(graph))]

    queue = list(range(0, len(graph)))
    while len(queue) > 0:
        u = min(queue, lambda v: distance[v])
        queue.remove(u)
        for edge in graph[current]:
            (v, w) = edge
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                parent[v] = u
    return (distance, parent)

V binární haldě by to bylo $Θ (V lo g V + E lo g V)$ a ve Fibonacciho haldě $Θ (V lo g V + E)$ .

Dijkstrův algoritmus lze optimalizovat, pokud nás zajímá jen nejkratší cesta mezi dvěma konkrétními vrcholy:

Funkce vrátí výsledek, jakmile je cílový vrchol vytažen z fronty.
Můžeme hledat zároveň ze začátku a konce pomocí dvou front a skončit, jakmile se někde potkají.
Můžeme přidat potenciál — dodatečnou heuristickou váhu.

Minimální kostra grafu (Minimum spanning tree)

Kostra grafu $G$ je strom $T$ takový, že $V (T) = V (G)$ .

Minimální kostra má nejmenší možnou váhu $d_{G}^{w} (T)$ .

Kruskalův algoritmus

Hladové hledání minimální kostry grafu.

def kruskal(graph: List[List[Tuple[int, int]]]) -> List[Tuple[int, int]]:
    # graph is an adjacency list of tuples (dst, weight)
    # returns a list of edges in the MST
    # sort all edges by their weight
    edges = [(w, src, dst) for src in range(0, len(graph)) \
        for (dst, w) in graph[src]]
    edges.sort()
    # initialize the MST to an empty "set"
    mst = []
    for e in edges:
        (w, u, v) = e
        # if no cycles get created by adding (u, v), add (u, v)
        if acyclic(graph, edges + [(u, v)]):
           mst.append((u, v))
    return F

Jarníkův (Primův) algoritmus

Je rychlejší než Kruskal, ale funguje jen na souvislých, vážených grafech.

Inicializuj strom $T$ s libovolným vrcholem $u$ a prázdnou množinou hran.
Přidej do stromu jednu hranu. A to takovou, že jeden konec je ve stromě $T$ a druhý ne. Pokud je takových hran více, zvol tu s nejmenší vahou.
Opakuj 2. krok, dokud strom není kostra.

Borůvkův algoritmus

Je taky rychlejší než Kruskal a funguje i na nesouvislých grafech.

Pro každý vrchol inicializuj komponentu souvislosti — množinu, kde je jen ten vrchol. Je to vlastně les jednoprvkových stromů.
Pro každou komponentu najdi hranu, která vede do jiné komponenty. Pokud je jich víc, vyber tu s nejmenší vahou.
Opakuj 2. krok, dokud jde některé komponenty spojit.