Algoritmusok és adatszerkezetek

Ezen az oldalon egy rövid elméleti bevezető után a leggyakoribb programozási technikákat, algoritmusokat és adatszerkezeteket nézzük meg. A pszeudokódos áttekintés mellett Java megvalósítást is látunk.

Table of Contents

Bonyolultságelmélet

Vegyünk egy egyszerűbb algoritmust, például a buborékrendezést, és számoljuk össze, hogy hány lépésből áll!

1 ok = true
2 while ok
3     ok = false
4     for i = 1 to N-1
5         if A[i] > A[i+1]
6             A[i] <-> A[i+1]
7             ok = true

Vezessük be a következő jelöléseket:

  • $c_1, c_2, ... c_7$: az első, második, …, hetedik sor egyszeri végrehajtási költsége,
  • $t$: a 2. sortól kezdődő ciklus lépéseinek a száma,
  • $p$: az 5. sorban a feltétel bekövetkezésének a valószínűsége.

Az utasítások végrehajtásainak a száma általános esetben:

  • 1: 1
  • 2: t+1
  • 3: t
  • 4: t*(N-1)
  • 5: t*(N-1)
  • 6: p*t*(N-1)
  • 7: p*t*(N-1)

Így az algoritmus teljes ára: $c_1 + c_2*(t+1) + c_3*t + c_4*t*(N-1) + c_5*t*(N-1) + c_6*p*t*(N-1) + c_7*p*t*(N-1)$. Átrendezéssel adódik: $t*N*(c_4+c_5+p*c_6+p*c_7) + t*(c_2+c_3-c_4-c_5-p*c_6-p*c_7) + (c1+c2)$. A zárójelben található értékek konstansok, amelyeket rendre a, b és c-vel jelölve a képlet tovább egyszerűsödik: $a*t*N + b*t + c$. Ez viszont még mindig túl összetett, és nem igazán alkalmas más algoritmusokkal való összehasonlításra. Nézzük meg a legjobb, a legrosszabb és az átlagos esetet!

  • Legjobb eset: ha a tömb eleve rendezett, akkor a külső cilus csak egyszer fut le, így a lépések száma $a*N + b$ megfelelő a és b konstansokra.
  • Legrosszabb eset: t=N+1, tehát a lépések száma $a*N^2 + b*N + c$, megfelelő konstansokra.
  • Átlagos eset: t=N/2-vel számolva szintén $a*N^2 + b*N + c$, megfelelő konstansokra.

Az algoritmusoknál elsősorban az átlagos esetekkel érdemes foglalkozni, figyelembe véve azt, hogy a legrosszabb eset ne legyen elfogadhatatlanul rossz, ill. a bekövetkezési valószínűsége kellően kicsi legyen. Ha $N$ kellően nagy, akkor a $b*N$ és a $c$ tag elhanyagolhatóvá válik. Az $a$ pontos értékének kiszámítása bonyolult, ráadásul mivel nem függ a bemenettől, azt is el szoktuk hagyni. Így azt mondhatjuk, hogy átlagos és legrosszabb esetben a lépések száma a bemenet méretének a négyzetével ($N^2$) arányos, míg legjobb esetben lineáris ($N$).

Most vezessük be néhány jelölést, amelyeket aszimptotikus jelölésnek nevezünk:

  • $O$: az algoritmus komplexitása legfeljebb ennyi.
  • $o$: az algoritmus komplexitása legfeljebb ennyi úgy, hogy ezt már nem éri el.
  • $\Theta$: az algoritmus komplexitása minden esetben pontosan ennyi.
  • $\Omega$: az algoritmus komplexitása legalább ennyi.
  • $\omega$: az algoritmus komplexitása legalább ennyi úgy, hogy ennél mindig nagyobb.

A gyakorlatban szinte kizárólag az $O$ jelölést használjuk, amit úgy ejtünk ki, hogy ordó. Zárójelben adjuk meg a komplexitást, amit kis n betűvel jelölünk. Ezzel a jelöléssel a buborékrendezés aszimptotikus komplexitása $O(n^2)$.

Az algoritmusok komplexitásával a bonyolultságelmélet foglalkozik. Néhány nevezetes algoritmus bonyolultság:

  • Konstans, azaz $O(1)$: a futási idő nem függ a bemenet méretétől. Ilyen művelet például a beszúrás egy láncolt lista elejére.
  • Logaritmikus, azaz $O(lg(n))$: a futási idő legnagyobb részt a bemenet (általában kettes alapú) logaritmusától függ. Ilyen művelet például a beszúrás egy kiegyensúlyozott keresőfába. Hogy érezzük ennek a súlyát: ezer elem esetén a logaritmus 10, egymillió esetén 20, tehát ez egy elég lassan növekvő érték. Bár nem konstans, mert tetszőleges konstansra tudunk olyan inputot gyártani, amire elvben nagyobb lesz a logaritmus értéke, mégis, a gyakorlatban szinte konstans időnek tekinthető. Gondolunk csak bele: mondjuk száz lépés végrehajtása szinte pillanatok alatt végbemegy, de mekkorának kell lennie annak az inputnak, melyek a kettes alapú logaritmusan eléri a százat!
  • Lineáris, azaz $O(n)$: tehát az algoritmus futási ideje egyenesen arányos a bemenet méretével. Ilyen például egy rendezetlen listában megkeresni a legkisebb elemet.
  • $O(n*lg(n))$: ennek elsősorban a rendező algoritmusoknál van jelentősége. Ebbe a kategóriába esik például a gyorsrendezés. A lassan növekvő $lg(n)$ tag miatt nem sokkal rosszabb egy ilyen algoritmus a lineárisnál.
  • Négyzetes, azaz $O(n^2)$: amint fent is láttuk. Ezernek a négyzete egymillió egymilliónak viszont egybillió; nem mindegy, hogy egy egymillió elemből álló tömb rendezése egybillió vagy húszmillió lépésből áll.
  • Polinomiális, azaz $O(n^p)$ valamilyen p konstansra. A fentiek tulajdonképpen mind tekinthetők polinomiálisnak. Ezt az osztályt P-vel szokás jelölni. Persze nagyon nem mindegy, hogy egy algoritmus konstans vagy $O(n^4)$ (ez utóbbi esetben eg 100 méretű inputon a lépések száma százmilliós nagyságrendű), de ahogy majd mindjárt látni fogjuk, ennek mégis nagyon nagy a jelentősége.
  • Exponenciális, pl. $O(2^n)$, vagy $O(n!)$, esetleg $O(n^n)$. Ezeket a megoldásokat nyers erőnek (brute force) is szoktuk hívni, és tipikusan csak nagyon kicsi inputra futnak le értelmes időben. Még a legegyszerűbb kettő hatvány esetében is a 10 méretű inputra a lépések száma ezres, 20-ra milliós nagyságrendű, 100-ra pedig nincs számítógép, amely értelmes időn belül végezne. Így ezek az algoritmusok általában nem elfogadhatóak például egy feladat megoldása során. Egy példa erre: a rendezést úgy is megoldhatnánk, hogy legeneráljuk az összes lehetséges sorrendet, és kiválasztjuk azt, amelyik a helyes sorrendet adja. Ennek a komplexitása $O(n!)$. Még egy 10 elemű tömb esetén is a lépések száma milliós nagyságrendű, 20 elemnél kivárhatatlan.
  • Az NP-teljes osztály: a számítástudomány legnagyobb megoldatlan elméleti kérdése erre az osztályra vonatozik. Láthattuk, hogy az exponenciális megoldások elfogadhatatlanul lassú futási időt eredményeznek. Vannak olyan feladatok, melyekre jelenleg exponenciális futási idejű algoritmust ismerünk, ugyanakkor létezik polinomiális idejű olyan algoritmus, amely eldönti, hogy egy megoldás az eredeti feladat optimális megoldása-e. A legismertebb ilyen feladat az utazó ügynök probléma (https://hu.wikipedia.org/wiki/Az_utazó_ügynök_problémája): adott n darab város, a városok között utak, és a feladat egy olyan körút keresése, amely mindegyik várost pontosan egyszer érint, ugyanoda tér vissza, és a megtett út a lehető legrövidebb. (A gráfelméletben ezt Hilbert görbének nevezzük.) Számos egyéb algoritmus van, amely polinomiális időben visszavezethető az utazó ügynökre; ez azt jelenti, hogy ha az utazó ügynöknek lenne polinomiális megoldása, akkor azoknak is lenne. Az NP a nemdeterminisztikus polinomiális idő rövidítése, azaz azokat az algoritmusokat soroljuk ide, amelyek polinomiális időben ellenőrizhetőek. Az ebbe tartozó algoritmusokat két fő csoportba sorolhatjuk: az egyik az eleve polinomiális algoritmusok, a másik pedig az, ahova az utazó ügynök is tartozik. A kérdés az, hogy ez a két halmaz egybeesik-e vagy sem. A legtöbb tudós azt sejti, hogy a kettő nem esik egybe, de ezt még senkinek sem sikerült bizonyítania. A dolognak egyébként praktikus jelentősége is van: ha sikerülne polinomiális idejű algoritmust találni az utazó ügynök problémára, akkor polinom időben vissza tudjuk vezetni a nyílt kulcsú titkosítás dekódolását a privát kulcs nélkül, így az egész technológia gyakorlatilag mehetne a kukába. Ennek a valószínűsége viszont igen csekély. Ezzel kapcsolatos összefoglaló a Wikipédián, angolul: https://en.wikipedia.org/wiki/P_versus_NP_problem.

A későbbiekben meg fogjuk adni az egyes műveletek bonyolultságát.

Rekurzió

A rekurzió nem igazán algoritmus, hanem programozási technika. Számos algoritmikus feladat megoldását könnyíti meg, emiatt fektetünk rá külön hangsúlyt. Logikailag a rekurzió sokban hasonlít a teljes indukcióval történő bizonyításra: ahogy a matematikában megmutatjuk az azonosságot a kisebb értékekre, majd feltételezve, hogy n-1-re már igaz az állítás, n-re is megmutatjuk, itt ugyanúgy a kisebb értékeknél visszaadjuk a megoldást, a nagyobbaknál pedig visszavezetjük a kisebbekre. Néhány általános szempont:

  • Technikailag a rekurzió azt jelenti, hogy egy függvény meghívhatja saját magát.
  • Rekurzió kötelező a terminálási feltétel, azaz az az eset, amikor nincs rekurzív hívás, egyébként végtelen rekurzió következik be, ami viszonylag gyorsan veremtúlcsorduláshoz (stack overflow) vezet.
  • A rekurzív hívásnál az átadott paraméternek el kell térnie (praktikusan a terminálási feltétel irányába, bár ez nem kötelező) a kapott paramétertől, különben szintén végtelen rekurzió lesz az eredmény.
  • A rekurzió mindig megvalósítható iteratív módon is, verem segítségével, és általában az iteratív megvalósítás gyorsabban fut mint a rekurzív. A rekurzív viszont tömörebb kódot eredményez, és kevesebb változóra van hozzá szükség.
  • Több rekurzív hívás is lehet egy függvényben, nemcsak egy. Ez esetben viszont jó eséllyel többször hívjuk meg a függvényt ugyanazzal a paraméterrel. Praktikus ilyenkor egy tömbben feljegyezni a már egyszer kiszámított értékeket, és az újabb rekurzív hívásnál onnan visszaadna ahelyett, hogy ismét kiszámolnánk.
  • Előfordulhat az is, hogy a rekurzív hívás nem közvetlen, hanem közvetett, pl. az f() függvény meghívja a g()-t, a g() a h()-t, a h() pedig az f()-et. Ezt szimultán rekurziónak hívjuk, és itt is gondoskodnunk kell a terminálásról.

Sima rekurzió

Sima rekurzió során van közvetlen rekurzív hívás. Lássunk néhány feladatot ezzel kapcsolatban!

Faktoriális

A rekurziók helló világa a faktoriális. Az 1 faktoriálisa 1, ez a terminálási feltétel, tetszőleges n > 1-re pedig n szorozva n-1 faktoriálisa. Hibakezelés nélkül, kissé elnagyoltan a megvalósítás:

public class Factorial {
    public static int factorial(int n) {
        if (n <= 1) return n;
        else return n * factorial(n-1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(10));
    }
}

Látható a factorial() rekurzív hívás.

Fibonacci

A Fibonacci számok definíciója: 0-ra 0, 1-re 1, tetszőleges 1-nél nagyobb egészre pedig az előző kettő Fibonacci szám összege. Rekurzívan rendkívül egyszerű megvalósítani (szintén eltekintve a hibakezeléstől):

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        else return fibonacci(n-1) + fibonacci(n-2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
}

Ezzel viszont rátapintottunk a rekurzió lehetséges hátulütőjére: különböző ágakon valójában nagyon sokszor kiszámoljuk ugyanazt. Próbáljuk meg végrehajtani a fenti programot mondjuk 46-ra (ez ugyanis a legnagyobb olyan szám, melynek Fibonacci értéke még belefér az int-be). Nálam közel 10 másodpercig tartott a kiszámolása, holott gyakorlatilag minimális memóriahasználat mellett 46 darab összeadásról van szó.

Ha mindenképpen ragaszkodunk a rekurzív megvalósításhoz, akkor alkalmazhatjuk a következő trükköt (melyet általában használhatunk, nemcsak itt): érdemes a már kiszámolt részeredményeket elmenteni a memóriában, és ha egy másik ágon ugyanazzal a paraméterrel szeretnénk kiszámolni, akkor elég az elmentett értéket visszaadni, nem kell újra kiszámolni. A kissé elnagyolt megoldás az alábbi:

public class FibonacciImproved {
    private int[] fibonacciValues;

    private int fibonacciImprovedRecursion(int n) {
        if (fibonacciValues[n] < 0) {
            fibonacciValues[n] = fibonacciImprovedRecursion(n-1) + fibonacciImprovedRecursion(n-2);
        }
        return fibonacciValues[n];
    }

    public int fibonacciImproved(int n) {
        fibonacciValues = new int[n+1];
        fibonacciValues[0] = 0;
        fibonacciValues[1] = 1;
        for (int i = 2; i <= n; i++) {
            fibonacciValues[i] = -1;
        }
        return fibonacciImprovedRecursion(n);
    }

    public static void main(String[] args) {
        System.out.println(new FibonacciImproved().fibonacciImproved(46));
    }

}

Itt kihasználtuk azt, hogy a Fibonacci nem lehet negatív, és -1-re inicializáltuk a tömböt. Általános esetben ez nem szép megoldást, helyette csomagoló (wrapper) osztályokat érdemes használni, és null értékkel jelezni az adat hiányát, sőt, ha a programozási nyelv engedi (pl. Scala vagy Java 8+), akkor az Option típust.

A Fibonaccit a valóságban iteratívan érdemes megvalósítani. Ez persze már nem annyira elegáns mint a rekurzió; kissé elnagyoltan és lényegre törően:

public class FibonacciIterative {
    public static int fibonacci(int n) {
        int previous = 0;
        int actual = 1;
        for (int i = 2; i <= n; i++) {
            int temp = actual;
            actual += previous;
            previous = temp;
        }
        return actual;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
}

Ördöglakat

Összegszám

Kamion

Szimultán rekurzió

Kifejezés kiértékelése

Hilbert görbe

TODO: Fenyő, virág

Postfix-infix konverzió

Rendező algoritmusok

A rendezés alapfeladata: adott egy tömb, melynek elemeit adott szempont szerint kell sorba rendezni. A rendezés lehet stabil van nem stabil. Stabil rendezésről akkor beszélünk, ha az egyenlő elemek mindenképpen megtartják eredeti sorrendjüket, nem stabil esetben ez nem garantált. Ennek akkor van jelentősége, ha mondjuk objektumokat rendezünk egy attribútum alapján, viszont vannak olyan attribútumok, melyek nem befolyásolják a rendezés sorrendjét.

Négyzetes algoritmusok

Ezek az algoritmusok viszonylag egyszerűek, jól érthetőek és gyorsan meg tudjuk valósítani a futási idejük viszont $O(n^2)$. Kisebb méretű tömbök (pl. 100 elem) rendezésére kiválóan alkalmasak, nagyobb tömbök esetén viszont más megoldást érdemes alkalmaznunk.

Kiválasztó rendezés

Beszúró rendezés

Buborékrendezés

O(n*log(n)) algoritmusok

Ezek az algoritmusok nagy tömbök esetén jóval gyorsabban a fent bemutatott módszereknél. A kettes alapú logaritmus rendkívül lassan növekszik: ezer esetén kb. 10, egymillió esetén kb. 20, egymilliárd esetén kb. 30. A gyakorlati előnyük mellett az elméleti jelentőségük is nagy, mivel általános esetben, tehát akkor, amikor két elemről csak azt tudjuk eldönteni, hogy melyik a kisebb, vagy egyenlőek-e, bizonyíthatóan nincs olyan módszer, ami aszimptotikusan jobb lenne ennél. Ugyanakkor ezek sokkal bonyolultabbak a fentieknél; hosszabb ideig tart megvalósítani, nehezebb megérteni, nehezebb átlátni.

Kupacrendezés

Gyorsrendezés

Ez az egyik leggyakoribb rendezőalgoritmus. Ennek az az oka, hogy futási ideje átlagos esetben $O(n*log(n))$, és a konstans a legkisebb a maga kategóriájában. Módszer:

  • Válasszunk ki egy elemet (például az elsőt), ez lesz a pivot. Egy-egy hivatkozást balról ill. jobbról indítva ha olyan elempárhoz érkezünk, hogy a bal oldali nagyobb, a jobb oldali pedig kisebb mint a kiválasztott elem, akkor cseréljük fel. Ezzel létrejött két rendezetlen rész úgy, hogy a bal oldaliban az elemek kisebbek vagy egyenlőek a jobb oldali elemekhez képest.
  • Hajtsuk végre a fenti algoritmust a bal, majd a jobb részen.

A pszeudokód:

GYORSRENDEZÉS(A,p,r)
    if p<r
        q=FELOSZT(A,p,r)
        GYORSRENDEZÉS(A,p,q)
        GYORSRENDEZÉS(A,q+1,r)

FELOSZT(A,p,r)
    x=A[p]
    i=p-1
    j=r+1
    while 1
        do j-- while A[j]>x
        do i++ while A[i]<x
        if i<j A[i]<->A[j]
        else return j

Java megvalósítás:

public class QuickSort {
    private int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public void quickSort() {
        quickSort(0, array.length-1);
    }

    private void quickSort(int p, int r) {
        if (p < r) {
            int q = divide(p, r);
            quickSort(p, q);
            quickSort(q+1, r);
        }
    }

    private int divide(int p, int r) {
        int x = array[p];
        int i = p - 1;
        int j = r + 1;
        while (true) {
            j--;
            while (array[j] > x) j--;
            i++;
            while (array[i] < x) i++;
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            } else {
                return j;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 7, 8, 3, 4, 1, 9, 2, 1, 6, 4};
        QuickSort qs = new QuickSort(array);
        qs.quickSort();
        for (int i = 0; i < array.length-1; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println(array[array.length-1]);
    }
}

Elemzés:

  • A rendezés nem stabil.
  • A futási idő legjobb és átlagos esetben is $O(n*log(n))$.
  • A legrosszabb esetben viszont $O(n^2)$; például abban az esetben fordul ez elő, ha a tömb eleve rendezett, vagy ha mindegyik elem egyenlő.
  • Különböző elemek esetén garantálni lehetne az $O(n*log(n))$-t, ugyanis lineáris időben megkereshető a középső elem. De ezzel jelentősen megnő az O által elrejtett konstans, így nem érdemes alkalmazni. Ráadásul a csupa egyenlő elemből álló inputon ez sem segít.
  • A legrosszabb eset kezelésére a véletlenítést használhatjuk: első lépésben felcseréljük az első elemet egy véletlennel, és úgy hajtjuk végre a rendezést. Ebben az esetben a legrosszabb eseté még mindig $O(n^2)$, viszont annyit ezzel elérünk, hogy nem lehet előre gyártani olyan esetet, ahol ez kijön.

A Java alapértelmezett rendező algoritmusa a fenti módszer tovább gondolása, Dual Pivot gyorsrendezés, amely egy helyett kettő pivot értékkel dolgozik, ráadásul úgy lett megvalósítva, hogy az egyenlő elemek sorrendjét is megtartja. Egy példakód az alábbi:

import java.util.*;

public class QuickSortJava {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(5, 7, 8, 3, 4, 1, 9, 2, 1, 6, 4);
        Collections.sort(list);
        System.out.println(list);
    }
}

Összefésülő rendezés

Lineáris algoritmusok

Amint arról volt szó, általános esetben a leggyorsabb rendezési algoritmusos futási ideje $O(n*log(n))$, ez alá elméletben sem lehet menni. Az ennél gyorsabb (tehát lineáris időben lefutó) módszerek mindegyike kihasznál valamilyen speciális dolgot az inputtal kapcsolatban, pl. azt, hogy nem túl nagy egész szám.

Számláló rendezés

Számjegyes rendezés

Edényrendezés

Mediánok és rendezett minták

Legkisebb elem

i. elem

Dinamikus programozás

Mátrixszorzás

Leghosszabb közös részsorozat

Optimális bináris keresőfa

Pénzváltás

Egyirányú utazó ügynök

Mohó algoritmusok

Esemény kiválasztása

Hátizsák feladat

Huffmann kód

Pénzváltás

Optimális tárolás

Minimális lefedő halmaz

Backtrack

Adatszerkezetek

Elemi adatszerkezetek

Verem

Sor

Láncolt lista

Bináris keresőfák

Gyökeres fa

AVL fa

Piros-fekete fa

A bináris keresőfák továbbgondolásai

Skiplist

Dinamikusan rendezett minta

Intervallum fa

B-fa

Hasító táblázatok

Az alapprobléma

Angolul hash table. A feladat olyan adatszerkezet létrehozása, melyben az alapműveletek (beszúr, keres, töröl) futásideje közel konstans. Tegyük fel, hogy egy elem csak egyszer fordulhat elő. Alapfeladat: a keres azt adja vissza, hogy az adott elem benne van-e a gyűjteményben.

Valójában ezt azonnal általánosíthatjuk, mellyel egy új, igen hasznos adatszerkezethez érkezünk. Az általánosítás alapja a következő. A gyűjteményekben kerülő elemek a legtöbb esetben nem primitív típusok, hanem adatstruktúrák (osztályok), melyek attribútumait a gyűjtemény szempontjából két csoportba oszthatjuk: vannak, amelyek az összehasonlításnál számítanak (azaz ha két objektum legalább egy ilyen mezőben különbözik, akkor különbözőnek tekintjük), és vannak, amelyek nem (ha csak ebben különbözik két objektum, akkor azokat az összehasonlításnál egyenlőnek tekintjük). Azokat a mezőket, melyek számítanak az összehasonlításnál, együttesen nevezzük kulcsnak, azokat pedig, amelyek nem számítanak, értéknek.

Most tegyünk még két lépést annak érdekében, hogy könnyebben tudjuk tárgyalni témát:

  • A kulcs típusa legyen egész szám. Egy elméleti megoldás általános esetben: képezzünk a mezőkből JSON formátumot, melyből vissza tudjuk állítani az eredeti struktúrát, majd ezután vegyük a JSON-ban található karakterek ASCII kódját, és azokból képezzünk számot. Az egyszerűség érdekében legyen a kulcs típusa a példákban egész (int). Általános esetben persze ez nem elég, de erre a problémára majd később visszatérünk.
  • Az érték bármilyen struktúra lehet; az egyszerűség érdekében a példákban string lesz a típusa. (Egyébként ezzel az általánosítást nem sértettük meg, ugyanis a string tartalmazhat pl. JSON-t).

Ezzel megalkottuk az asszociatív tömb (angolul map) fogalmát, mely kulcs-érték párokból áll. Egy kulcshoz többnyire egy érték tartozhat, bár általánosíthatjuk a megvalósítást úgy, hogy az érték típusa lista, és ez esetben többször is szerepelhet ugyanaz a kulcs. Vegyük észre, hogy ha az érték típusa logikai lenne (vagy string esetén a true és false értékek), akkor valójában halmazt valósítottunk meg. Egyébként pont innen indultunk, és egy olyan adatszerkezetnél tartunk, mely viszonylag egyszerűen visszavezethető halmazra (és a gyakorlatban alkalmazzák is egyébként ezt a visszavezetést).

Közvetlen címzésű táblák

Első ötlet: hozzunk létre közvetlen címzésű táblázatot. A táblázat mérete legyen akkora, amennyi az elméletileg előfordulható legnagyobb kulcs értéke, a táblázat cellái pedig az tartalmazza az értékeket. Vannak bizonyos feladat típusok, amelyeknél ez a módszer kiválóan működik. Vegyük például a magyarországi települések irányítószámait mint kulcsokat, és a településneveket, mint értékeket. Ez esetben felveszünk egy tízezer elemből álló tömböt. Műveletek:

  • Beszúrás: konstans időben elvégezhető, egyetlen címzéssel. Tehát például megmondjuk azt, hogy a 2750-es irányítószámú település neve Nagykőrös, az a tömb 2750. cellájának a Nagykőrös értékre állítását jelenti.
  • Lekérdezés: szintén konstans idejű. Ez esetben kiolvassuk például a táblázat 2750. cellájában található értéket.
  • Törlés: ugyancsak konstans idejű. Ebben az esetben a cella adott elemét üresre (null) állítjuk.

Lássunk egy (hibakezelést nem tartalmazó, egyszerűsített) megvalósítást Java-ban:

public class DirectAddress {
    private String[] towns = new String[10000];

    public void setZipCode(int zipCode, String town) {
        towns[zipCode] = town;
    }

    public String getTown(int zipCode) {
        return towns[zipCode];
    }

    public static void main(String[] args) {
        DirectAddress zipCodes = new DirectAddress();
        zipCodes.setZipCode(2750, "Nagykőrös");
        zipCodes.setZipCode(6000, "Kecskemét");
        zipCodes.setZipCode(6720, "Szeged");
        System.out.println(zipCodes.getTown(2750));
    }
}

Ugyanakkor van ennek a megoldásnak két hátulütője:

  • Az elemek bejárási ideje nem az elemek számával arányos, hanem a teljes táblázat méretével. Például a 10000 alatti számok többségéhez nem tartozik település, például az első 1000 számhoz.
  • Általános esetben el se fér egy ilyen táblázat a memóriában, de ha elfér is, borzasztóan helypazarló. A fenti példában helyet foglaltunk azoknak az irányítószámoknak is, amelyek nem léteznek. De képzeljük el a fordított esetet: a kulcs a településnév, és az érték az irányítószám. Ez esetben iszonyatosan nagy számok jöhetnek ki az ASCII értékekből, elképzelhetetlenül nagy méretű memóriára lenne szükség, miközben alig pár ezer értékpárt szeretnénk csak tárolni.

A közvetlen címzés tehát csak speciális esetekben használhatóak, a továbbgondolásra viszont ötletet adnak.

Hasítás

A közvetlen címzéses módszer továbbgondolása: ugyanabba a cellába ne egyetlen elem kerülhessen. Azt a függvényt, amely eldönti, hogy egy elem melyik cellába kerüljön, hasító függvénynek nevezzük. Erről még részletesebben lesz szó; most tegyük fel, azt, hogy a hasító függvény a következő: a kulcs számértékét osszuk el a tömb kapacitásával, és vegyük a maradékot. A maradékképzést modulo-nak hívjuk. Ha tehát mondjuk a kapacitás 10, akkor az 5-ös, a 15-ös, a 25-ös stb. kulcsú elem mind ugyanabba a cellába kerül. Az ütközéseket valahogy fel kell oldani. Ennek egy lehetséges módszere a láncolt lista. Műveletek:

  • Beszúrás: a hasító függvény segítségével számoljuk ki, hogy melyik cellába kell beszúrni az elemet. Ha ott még nincs semmi, szúrjuk be. Ha már van, akkor képezzünk láncolt listát, és szúrjuk be, pl. az elejére.
  • Keresés: ugyancsak képeznünk kell a cellaértéket, majd végig kell lépkedünk az abban a cellában található elemeken.
  • Törlés: keressük meg az elemet a keresésnél megadott módon, és töröljük, mintha láncolt listából törölnénk egy elemet.

A hasító függvénynek minden lefutáskor ugyanarra az inputra ugyanazt az outputot kell adnia, és praktikusan gyorsnak (konstans idejűnek) kell lennie, különben nem sok értelme lenne ennek az adatszerkezetnek. Lássuk az egyes műveletek futási idejét:

  • A beszúrás minden esetben konstans, mivel a hasító függvény konstans idejű, és a beszúrás a láncolt lista elejére szintén konstans.
  • A keresés és a törlés ideje attól függ, hogy mennyi elem van az érintett cellában. Leggyorsabb esetben ez konstans, legrosszabb esetben viszont lineáris. A legrosszabb eset akkor áll fenn, ha olyan szerencsétlen hasító függvényt választunk, amely mindegyik értékhez ugyanazt a cellát rendeli. Ha a tömb mérete m, és n darab elem van benne, akkor egyenletes hasító függvény esetén ezeknek a műveleteknek a futási ideje $O(1 + n/m)$. Ha pont akkora tömböt foglalunk le, amennyi az elemszám, akkor a legjobb esetben a keresés és a törlés konstans idejű. Legrosszabb esetben tehát lineáris, átlagos esetben pedig a hasító függvénytől függ. Mivel jó hasító függvényt találni nem egyszerű, azt külön tárgyaljuk. (Majd látni fogjuk, hogy a modulo 10 hasító függvény nem a legjobb.)

Lássunk egy Java megvalósítást!

public class MyHashTable {
    class LinkedListOfElems {
        int key;
        String value;
        LinkedListOfElems next;

        LinkedListOfElems(int key, String value, LinkedListOfElems next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private int capacity;
    private LinkedListOfElems[] elements;

    public MyHashTable(int capacity) {
        this.capacity = capacity;
        elements = new LinkedListOfElems[capacity];
        for (int i = 0; i < capacity; i++) {
            elements[i] = null;
        }
    }

    private int myHashCode(int key) {
        return key % capacity;
    }

    public void insert(int key, String value) {
        LinkedListOfElems linkedListOfElems = findLinkedListOfElems(key);
        if (linkedListOfElems != null) {
            linkedListOfElems.value = value;
        } else {
            int bucket = myHashCode(key);
            elements[bucket] = new LinkedListOfElems(key, value, elements[bucket]);
        }
    }

    public String find(int key) {
        LinkedListOfElems linkedListOfElems = findLinkedListOfElems(key);
        if (linkedListOfElems != null) {
            return linkedListOfElems.value;
        } else {
            return null;
        }
    }

    private LinkedListOfElems findLinkedListOfElems(int key) {
        int bucket = myHashCode(key);
        LinkedListOfElems actualElementContainer = elements[bucket];
        while (actualElementContainer != null) {
            if (key == actualElementContainer.key) {
                return actualElementContainer;
            } else {
                actualElementContainer = actualElementContainer.next;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        MyHashTable myHashTable = new MyHashTable(10);
        myHashTable.insert(5, "apple");
        myHashTable.insert(8, "banana");
        myHashTable.insert(15, "peach");
        System.out.println(myHashTable.find(5));
        System.out.println(myHashTable.find(8));
        System.out.println(myHashTable.find(15));
    }
}

A kód nem rövid, ráadásul nem tartalmaz hibakezelést, valamint törlést se.

Hasító függvények

Mivel a hasító függvényen múlik az, hogy a műveletek futási ideje átlagos esetben inkább a konstanshoz vagy inkább a lineárishoz lesznek-e közelebb, nagyon megfontoltan érdemes megválasztani. Szempontok:

  • Egyenletesség: az egyes cellákba egyforma eséllyel kerülhessenek elemek. Ilyenkor érdemes figyelembe venni a konkrét célra használt típus tapasztalati eloszlását. Egy példa: az emberek tárolására hasítófüggvényként használhatjuk az illető életkorát években kifejezve. Ez alapvetően jó, de jobb megoldást biztosít, ha figyelembe vesszük a korfát, és a fiatalabb korosztálynál az évet feloszthatjuk két külön cellába, idősebb korban pedig akár össze is vonhatunk életkorokat egy-egy cellába. De ha mondjuk a nyugdíjasokat szeretnénk ilyen módon nyilván tartani, akkor a fiatalabbakat célszerű összevonni, és a 60-as, 70-es korosztályban akár hónap szintre lebontva tárolni.
  • Lehetőleg függjön a kulcs minden bitnyi információjától. Ilyen értelemben a modulo 10 nem jó, mert az csak az utolsó számjegytől függ. A kettő hatványú maradék képzés szintén nem jó, mert abban az esetben az eredmény nem fog függni a szignifikánsabb (magasabb helyi értékű) bitektől. A prímszámokkal való osztás maradékképzése már sokkal jobb.
  • Hasonló elemek lehetőleg ne kerüljenek ugyanabba a cellába. A gyakorlatban sok a nagyon hasonló érték; célszerű olyan módszert választani, amely a hasonló elemeket nem ugyanabba a cellába teszi, sőt, lehetőleg távol kerüljenek egymástól. Ilyen értelemben a modulo módszer csak korlátozottan jó, mert az igaz, hogy az egymás melletti értékeket nem ugyanoda teszi, de bizonyos megvalósítások esetén az se jó, ha egymás mellé kerülnek.

Módszerek:

  • Osztásos módszer: a fent bemutatott maradékképzés: h(k)=k mod m.
  • Szorzásos módszer: legyen 0<A<1, pl. A=(gyök(5)-1)/2; h(k)=alsóegészrész(m*törtrész(k*A)). Ez a közeli értékeket is távolra címzi.
  • Univerzális hasítási technika: a fentiekkel továbbra is meg van az a probléma, hogy adott módszerre tudunk olyan inputot gyártani, melyre a futási idő lineáris lesz. Ha ezt mindenképpen el szeretnénk kerülni, akkor adott függvény helyett valósítsunk meg egy függvény osztályt, és véletlenszerűen válasszunk egyet közülük.

Nyílt címzés

A láncolt listáknak van egy nem elhanyagolható többlet memória használata. Ha ez nem megengedhető, és előre tudjuk a maximális elemszámot, akkor alkalmazhatjuk a következő módszert:

  • Foglaljuk le a maximális méretet. Mindegyik cellába egy érték kerül. Alapból minden cella legyen üres.
  • A hasító függvény nem egy számot, hanem egy sorozatot ad vissza: első elem, szükség esetén a második, harmadik stb., egészen a lehetséges tömbméretig. Ezt kipróbálási sorozatnak hívjuk, és ennek milyenségén áll vagy bukik ez az adatszerkezet.
  • Beszúrás: megpróbáljuk az első helyre beszúrni, ha nem üres, akkor a másodikra stb.
  • Keresés: megnézzük, hogy az első helyen van-e, utána a másodikon stb.
  • Törlés: megkeressük a fenti módon. Bevezetünk egy új, törölt állapotot, ami nem ekvivalens az üres értékkel. Beszúráskor az első törölt helyre szúrjuk be az értéket, keresésnél és törlésnél viszont ezeket át kell lépni, mintha ott valódi érték szerepelne. Ennek az az oka, hogy ha nem tennénk különbséget az üres és a törölt között, akkor egy másik érték keresésekor megakadhatnánk.

Kipróbálási technikák:

  • Lineáris kipróbálás: h(k,i)=(h'(k)+i) mod m, ahol h'(k) egy közönséges hasító függvény. Hátránya az elsődleges klaszterezés; előbb-utóbb szinte lineárissá válik minden művelet.
  • Négyzetes kipróbálás: h(k,i)=(h'(k)+c1*i+c2*i*i) mod m, ahol h'(k) egy kisegítő hasító függvény, c1 és c2 pedig nem 0 segédállandók. Hátránya a másodlagos klaszterezés. Ugyanis ha két kulcshoz ugyanaz a kezdeti érték tartozik, akkor a teljes kipróbálási sorozat megegyezik (m darab kipróbálási sorozat összesen).
  • Dupla hasítás: h(k,i)=(h1(k)+i*h2(k)) mod m, h1(k)=k mod m, h2(k)=1+(k mod m'), m' egy m-nél kicsivel kisebb egész. Ez m*m különböző kipróbálási sorozatot generál le, ami már elfogadható eredményt nyújt a klaszterezés megszüntetésében.

A Java és a hasító táblázatok

A Java nyelvbe igen mélyen be van ágyazva a hasítás. Mindenekelőtt az Object tartalmaz egy int hashCode() függvényt, amiről a fentiek alapján most már tudjuk, hogy lehet akár ez is: return 42;, de azt is tudjuk, hogy ez miért nem hatékony. Számos adatszerkezet van hasító táblákkal megvalósítva: az asszociatív tömbök közül a HashMap, a LinkedHashMap és a Hashtable, a halmazok közül pedig a HashSet és a LinkedHashSet. Bővebben erről a java-stdlibs|Java standard könyvtárak oldalon olvashatunk.

A gráfok ábrázolási módjai

A gráfok csúcsokból, élekből, és opcionálisan az éleken súlyokból állnak. Jelölések:

  • V - csúcshalmaz
  • E - élhalmaz
  • w: E → R súlyfüggvény

Háromféle ábrázolási mód terjedt el:

  • Élek felsorolása. Ebben az esetben az éleket (kezdőpont, végpont) formában felfűzzük egy láncolt listára, és az esetleges kísérő információkat is beletesszük a lista alapját képező struktúrába. Általában így szokták megadni a gráfot különböző feladatokban. Előnye az egyszerű tárolás és a kis helyigény (itt a legminimálisabb), hátránya viszont az, hogy nagyon lassúak lesznek az egyes gráfalgoritmusok.
  • Szomszédsági lista. Minden egyes csúcs esetén egy listára felfűzzük a szomszédait. Ritka gráfok esetén tömör. (Ritka gráf: |E| sokkal kisebb, mint |V*V|.) Annak eldöntése, hogy két pont között vezet-e él, nem hatékony. Súlyozott gráfok: a listában a szomszédok mellé kell tenni a súlyt is. Irányítatlan gráf esetén a listák összhossza |2*E|, irányított esetben |E|.
  • Szomszédsági mátrix: A=VxV csúcsmátrix, a csúcsok meg vannak sorszámozva. a[i,j]=1, ha (i, j) eleme E, 0 különben. Súlyozás esetén a[i,j]=súly, ha (i,j) eleme E, valamilyen nem használt speciális érték akkor, ha nem. Tetszőleges csúcspárról hatékonyan eldönthető, hogy eleme-e az élhalmaznak. Hatékony, ha E megközelíti V*V-t, egyébként tárpazarló. Nagy méretű gráfok esetén gyakorlatilag használhatatlan. Egyszerű, nem súlyozott gráfok esetén a mátrix elemei lehetnek bitek.

A tényleges megvalósítás a látszat ellenére meglehetősen bonyolult:

  • Létrehozunk egy GraphNeighbourList nevű osztályt, ami a csúcsok listáját tartalmazza. Az egyszerűség érdekében már a konstruktornál megadjuk a csúcsok számát, és azokat azonnal példányosítjuk, mégpedig 1-től sorszámozva. Mivel a Java-ban a sorszámozás 0-tól történik, a csúcsoké pedig célszerűen 1-től, az elejére beteszünk egy üres csúcsot.
  • A csúcs (Vertex) tartalmazza magát az él listát és a szomszédok lekérdezésénél a kliens ezt kapja vissza. Ez egyszerűsítés ahhoz képest, hogy a szomszédok tömbjét adná vissza, majd egyesével kérdezné le a súlyokat, így viszont a kliens feladata megkeresni a megfelelő értéket. Az él lista láncolt lista.
  • A csúcs tartalmaz egyéb információt is: egy távolság információt, egy másik csúcsot, valamint egy színt. Ezek nem kellenek az alap megvalósításhoz, viszont számos alap gráf algoritmus használja ezeket, így ahelyett, hogy azoknak mind magunknak kelljen megvalósítaniuk, az alapban benne van.
  • A csúcsok rendezési sorrendje a távolság információm mivel a legtöbb algoritmus azt minimalizálja.
  • Az él Edge tartalmaz egy hivatkozást a szomszédra, valamint egy súlyt, ami az egyszerűség érdekében egy egész szám.
  • Egy teljesen kész, általános megvalósítás még ennél is sokkal bonyolultabb, hiszen itt kihasználjuk a keretrendszer által nyújtott adatszerkezeteket, általános esetben viszont azokat is meg kellene valósítani.

Magának a gráfnak a megvalósítása:

import java.util.*;

public class GraphNeighbourList {
    private List<Vertex> vertice;
    private int numberOfVertice;

    public GraphNeighbourList(int numberOfVertice) {
        this.numberOfVertice = numberOfVertice;
        vertice = new ArrayList<Vertex>();
        vertice.add(null);
        for (int i = 1; i <= numberOfVertice; i++) {
            Vertex vertex = new Vertex(i);
            vertice.add(vertex);
        }
    }

    public int getNumberOfVertice() {
        return numberOfVertice;
    }

    public void addEdge(int v1, int v2, int weight) {
        getVertex(v1).addNeighbour(vertice.get(v2), weight);
    }

    public List<Edge> neighbours(int v) {
        return getVertex(v).getNeighbours();
    }

    public Vertex getVertex(int v) {
        return vertice.get(v);
    }
}

A csúcs megvalósítása:

import java.util.*;

public class Vertex implements Comparable<Vertex> {
    private int number;
    private List<Edge> neighbours = new LinkedList<Edge>();
    private Vertex predecessorVertex;
    private int distance;

    public Vertex(int number) {
        this.number = number;
    }

    public int getNumber() {
        return number;
    }

    public List<Edge> getNeighbours() {
        return neighbours;
    }

    public void addNeighbour(Vertex neighbour, int weight) {
        neighbours.add(new Edge(neighbour, weight));
    }

    public Vertex getPredecessorVertex() {
        return predecessorVertex;
    }

    public void setPredecessorVertex(Vertex predecessorVertex) {
        this.predecessorVertex = predecessorVertex;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    @Override
    public int compareTo(Vertex o) {
        return distance - o.distance;
    }
}

Az él megvalósítása:

public class Edge {
    private Vertex neighbour;
    private int weight;

    public Edge(Vertex neighbour, int weight) {
        this.neighbour = neighbour;
        this.weight = weight;
    }

    public Vertex getNeighbour() {
        return neighbour;
    }

    public int getWeight() {
        return weight;
    }
}

Gráf algoritmusok

Gráf bejárások

Szélességi keresés

Mélységi keresés

Vegyes gráf algoritmusok

Topologikus rendezés

Erősen összefüggő komponensek

Minimális feszítőfák

A Kruskal algoritmus

A Prim algoritmus

Legrövidebb utak

Adott egy irányított, súlyozott gráf, és a gráfnak két pontja. A feladat e két pont közötti legrövidebb út megkeresése. Változatok:

  • adott csúcsból induló utak megkeresése: nem tudunk olyan algoritmusról, amely a két pont közötti távolság kérdését aszimptotikusan gyorsabban dönti el, mint az összes csúcsra vonatkozót;
  • adott csúcsba érkező legrövidebb utak: ez az élek megfordításával visszavezethető az előző feladatra;
  • az összes csúcspár közötti legrövidebb utak problémája.

A negatív súlyú élek kérdése: ha nincs negatív összsúlyú kör, akkor a távolság jól definiált marad. Viszont ha negatív összsúlyú kör is van a gráfba, amely elérhető a kiinduló pontból, és a körből elérhető a célpont, akkor tetszőlegesen nagy negatív séta előállítható a kezdőpont és a végpont között a negatív súlyú körön körözve. Ekkor definíció szerint a két pont távolsága mínusz végtelen. Ha viszont valóan csak útról lehet szó (tehát olyan sétáról, amelyben nincs pontismétlődés), akkor a negatív súlyú kört tartalmazó gráfban is jól definiált a tetszőleges két pontot összekötő út, viszont ez a probléma NP-teljes.

Vezessük be a következő jelöléseket:

  • s: kezdő csúcs
  • d(s,r): az s és r csúcsok közötti legrövidebb út.
  • w(u,v): az (u,v) él súlya.

Az inicializáló eljárás a következő lesz minden esetben:

INICIALIZÁL(s)
    for minden v eleme V-re
        d[v] = végtelen
        ős[v] = NIL
    d[s] = 0

A következő segédeljárást szintén az összes algoritmus használja:

KÖZELÍT(u,v)
    if d[v] > d[u]+w(u,v)
        d[v] = d[u]+w(u,v)
        ős[v] = u

Tételek:

  • Minden s, u és v csúcsra, valamint (u,v) élre fennáll a következő egyenlőtlenség: d(s,v) <= d(s,u) + w(u,v).
  • Ha s -…→ u → v egy minimális s-v út, és d[u] már valóban a legrövidebb s-u út hossza, akkor a KÖZELÍT(u,v) meghívása után mindig teljesülni fog az, hogy d[v] a legrövidebb s-v út hossza lesz.

A fokozatos közelítés végeredményeképpen egy s gyökerű fa épül fel.

A Dijkstra algoritmus

A Dijkstra algoritmus megkeresi a legrövidebb utat két pont között egy olyan súlyozott, irányított gráfban, melyben nincs negatív súlyú él. Módszer: a már elért pontok közül kiválasztjuk azt a legrövidebbet, amelyiket még nem dolgoztuk fel, és meghívjuk a fenti KÖZELÍT eljárást mindegyik szomszédjára. Technika: prioritásos sor.

DIJKSTRA(s)
    INICIALIZÁL(s)
    S=üres
    Q=V
    while Q nem üres
        u=KIVESZ-MIN(Q)
        S=S U {u}
        for u minden v szomszédjára
            KÖZELÍT(u,v)

A fenti gráf ábrázolást feltételezve a Java megvalósítás, amely képernyőre írja az eredményt, a következő:

import java.util.*;

public class Dijkstra {
    public void shortestPathBetween(GraphNeighbourList graph, int startVertex, int destinationVertex) {
        PriorityQueue<Vertex> verticePriorityQueue = new PriorityQueue<Vertex>();
        for (int i = 1; i <= graph.getNumberOfVertice(); i++) {
            Vertex actualVertex = graph.getVertex(i);
            actualVertex.setPredecessorVertex(null);
            if (i == startVertex) {
                actualVertex.setDistance(0);
            } else {
                actualVertex.setDistance(Integer.MAX_VALUE);
            }
            verticePriorityQueue.add(actualVertex);
        }

        while (!verticePriorityQueue.isEmpty()) {
            Vertex actualShortestDistanceVertex = verticePriorityQueue.poll();
            if (actualShortestDistanceVertex.getNumber() == destinationVertex) break;
            for (Edge neighbouringEdge: actualShortestDistanceVertex.getNeighbours()) {
                Vertex actualNeighbour = neighbouringEdge.getNeighbour();
                if (actualNeighbour.getDistance() > actualShortestDistanceVertex.getDistance() + neighbouringEdge.getWeight()) {
                    actualNeighbour.setDistance(actualShortestDistanceVertex.getDistance() + neighbouringEdge.getWeight());
                    actualNeighbour.setPredecessorVertex(actualShortestDistanceVertex);
                    verticePriorityQueue.remove(actualNeighbour);
                    verticePriorityQueue.add(actualNeighbour);
                }
            }
        }

        LinkedList<Integer> resultList = new LinkedList<Integer>();
        Vertex actualVertex = graph.getVertex(destinationVertex);
        int minimumDistance = actualVertex.getDistance();
        while (actualVertex.getNumber() != startVertex) {
            resultList.addFirst(actualVertex.getNumber());
            actualVertex = actualVertex.getPredecessorVertex();
        }
        resultList.addFirst(startVertex);

        System.out.println(resultList);
        System.out.println("Minimal lenght: " + minimumDistance);
    }
}

Egy példa a használatra:

GraphNeighbourList graph = new GraphNeighbourList(7);
graph.addEdge(1,  2,  1);
graph.addEdge(1,  6,  8);
graph.addEdge(2,  3,  2);
graph.addEdge(2,  5,  6);
graph.addEdge(3,  4,  1);
graph.addEdge(3,  5,  2);
graph.addEdge(4,  1,  2);
graph.addEdge(4,  5,  2);
graph.addEdge(5,  6,  1);
graph.addEdge(6,  2,  1);
graph.addEdge(6,  7,  2);
new Dijkstra().shortestPathBetween(graph, 1, 6);

A Bellman-Ford algoritmus

Ez az algoritmus aszimptotikusan rosszabb, mint a Dijkstra, viszont működik olyan gráfokra is, amelyben van negatív súlyú él. Ha van negatív súlyú kör, akkor HAMIS értékkel tér vissza, különben IGAZ értékkel.

BELLMANN-FORD(s)
    INICIALIZÁL(s)
    for i=1 to V-1
        for minden (u,v) élre
            KÖZELÍT(u,v)
    for minden (u,v) élre
        if d[v]>d[u]+w(u,v)
            return HAMIS
    return IGAZ

A Java kód ennél kissé bonyolultabb:

import java.util.LinkedList;

public class BellmanFord {
    public void shortestPathBetween(GraphNeighbourList graph, int startVertex, int destinationVertex) {
        for (int i = 1; i <= graph.getNumberOfVertice(); i++) {
            Vertex actualVertex = graph.getVertex(i);
            actualVertex.setPredecessorVertex(null);
            if (i == startVertex) {
                actualVertex.setDistance(0);
            } else {
                actualVertex.setDistance(Integer.MAX_VALUE);
            }
        }

        int numberOfVertice = graph.getNumberOfVertice();
        for (int i = 1; i <= numberOfVertice - 1; i++) {
            for (int j = 1; j <= numberOfVertice; j++) {
                Vertex actualVertex = graph.getVertex(j);
                for (Edge edge: actualVertex.getNeighbours()) {
                    Vertex neighbourVertex = edge.getNeighbour();
                    int sumOfInstanceAndWeight = actualVertex.getDistance() + edge.getWeight();
                    if (neighbourVertex.getDistance() > sumOfInstanceAndWeight) {
                        neighbourVertex.setDistance(sumOfInstanceAndWeight);
                        neighbourVertex.setPredecessorVertex(actualVertex);
                    }
                }
            }
        }

        for (int j = 1; j <= numberOfVertice; j++) {
            Vertex actualVertex = graph.getVertex(j);
            for (Edge edge: actualVertex.getNeighbours()) {
                Vertex neighbourVertex = edge.getNeighbour();
                if (neighbourVertex.getDistance() > actualVertex.getDistance() + edge.getWeight()) {
                    System.out.println("The graph contains negative circle.");
                    return;
                }

            }
        }

        LinkedList<Integer> resultList = new LinkedList<Integer>();
        Vertex actualVertex = graph.getVertex(destinationVertex);
        int minimumDistance = actualVertex.getDistance();
        while (actualVertex.getNumber() != startVertex) {
            resultList.addFirst(actualVertex.getNumber());
            actualVertex = actualVertex.getPredecessorVertex();
        }
        resultList.addFirst(startVertex);

        System.out.println(resultList);
        System.out.println("Minimal lenght: " + minimumDistance);
    }

    public static void main(String[] args) {
        GraphNeighbourList graph = new GraphNeighbourList(7);
        graph.addEdge(1,  2,  3);
        graph.addEdge(1,  3,  2);
        graph.addEdge(2,  3,  -2);
        graph.addEdge(3,  4,  1);
        // graph.addEdge(4,  1,  -3);
        new BellmanFord().shortestPathBetween(graph, 1, 4);
    }
}

Ha a megjegyzésbe tett sortból kivesszük a megjegyzést, akkor olyan gráfot kapunk, amelyben van negatív kör.

Legrövidebb utak irányított körmentes gráfokban

Legrövidebb utak minden csúcspárra

Egy mátrixszorzás típusú módszer

A Floyd-Warshall algoritmus

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License