Betöltett grafikon
Betöltött gráf - digráf G = (V, X), amelyre a megadott funkciót rendel hozzá mindegyik ív egy grafikont valós szám - a hossza (w) x l (x) az ív. Megadhatja a súlyok mátrixát:
A zárt útvonal egy út (útvonal), amelynél az első és az utolsó csúcs egybeesik. Egy zárt utat, amely csak egyszer átmegy az egyes íveken (szélen), ciklusnak nevezik. Egy olyan ciklust, amely minden egyes csúcson áthalad, az egyszerű.
A lánc egy lezárt utat (útvonal), amely minden íven (élen) átmenni csak egyszer. Egy lánc, amely minden egyes csúcson áthalad az 1-es idő alatt egyszerűnek nevezhető.
Az út hossza (egy nem terhelt grafikon esetén) az ívek számát jelenti.
Az elérési út hossza (egy betöltött grafikon esetén) az ezen a pályán beérkező ívek súlya. A [v1 és vk csúcsok közötti minimális útvonal] az az útvonal, amelynek minimális hossza az összes többi út között [a v1-től vk-ig].
Dijkstra algoritmusa (a minta elérési útvonalának keresése a betöltött gráfban)
1. L * (s) = 0 értéket állítunk be, és feltételezzük, hogy ez a címke állandó. Minden v V V, v s s esetén l * (v) = set értéket állítunk be, és feltételezzük, hogy ezek a címkék ideiglenesek. Beállítjuk a p = s értéket.
2. Minden vOGp időbélyeggel: ha L * (v)> L * (p) + l (p, v), akkor L * (v) = L * (p) + l (p, v) és Q (v) = p. Ellenkező esetben az l * (v) és a Q (v) nem változtatható meg, pl. l * (v) = min (l * (t), l * (p) + cpv). (Az ötlet a következő :. Legyen p - top, hogy egy állandó címkét l * (p) az előző iterációban megtekintheti az összes top vOGp időbélyeggel jel l * (v) a felső vOGp helyébe l * (p) + l (. p, v), ha kiderül, hogy a címke l * (v)> l * (p) + l (p, v). Ebben az esetben azt mondjuk, hogy a v csúcs kapta címke a tetején p, így meg Q (v ) = p. segítségével ezek a további címkék majd vissza maga az út. Ha l * (v) J l * (p) + CPV, a címke ugyanaz marad.
3. Legyen V * az időbélyegek csúcsainak sorozata. Megtaláljuk a v * csúcsot, hogy l * (v *) = min l * (v), v 0 V *. Olvassa el az l * (v *) címkét az v * csúcs állandó értékeként.
4. Állítsa p = v * értéket. Ha p = t, akkor folytassa az 5. lépéssel (l * (t) - a minimális út hossza). Ellenkező esetben folytassa a 2. lépéssel.
5. Megtaláljuk a minimális sávot s-ről t-re, a Q (v) címkékkel: Π = s ... Q (t) t.