Wikiszótár

Johnson-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈjoxnʃonɒlɡoritmuʃ]

Főnév

Johnson-algoritmus

  1. (matematika)

Johnson-algoritmus

A Johnson-algoritmus egy gráfalgoritmus, amely a legrövidebb utak meghatározására szolgál iránymutatott, súlyozott gráfokban. Az algoritmus különösen hatékony ritka gráfok esetén, és képes negatív élhosszokat tartalmazó gráfokkal is működni (feltéve, hogy nincs negatív súlyú kör).


Alapötlet

A Johnson-algoritmus a Dijkstra-algoritmust és a Bellman-Ford-algoritmust kombinálja: 1. A Bellman-Ford-algoritmus segítségével először újrasúlyozza a gráf éleit, hogy az élhosszak ne legyenek negatívak. 2. Ezután a Dijkstra-algoritmust használja minden csúcsból kiinduló legrövidebb utak meghatározására az újrasúlyozott gráfban.


Lépések

1. Új csúcs hozzáadása

  • Hozzáadunk egy új csúcsot ((s)) a gráfhoz.
  • Az új csúcsot összekötjük az eredeti gráf minden csúcsával, (0) súlyú élekkel.

2. Bellman-Ford-algoritmus futtatása

  • Az új csúcs ((s)) kiindulópontként használva a Bellman-Ford-algoritmus segítségével meghatározzuk az összes többi csúcs távolságát ((h(v))) az (s)-től.
  • Ha a gráf tartalmaz negatív súlyú kört, az algoritmus leáll.

3. Él-súlyok újrasúlyozása

  • Az új súlyokat az alábbi képlettel számítjuk: [ w’(u, v) = w(u, v) + h(u) - h(v) ] ahol:
    • (w(u, v)) az eredeti él súlya,
    • (h(u)) és (h(v)) a Bellman-Ford által számított súlyok.
  • Ez az újrasúlyozás biztosítja, hogy minden (w’(u, v) ).

4. Dijkstra-algoritmus alkalmazása

  • Az újrasúlyozott gráfban minden csúcsból futtatjuk a Dijkstra-algoritmust.
  • Az eredeti súlyokat visszaszámítjuk az alábbi képlettel: [ d(u, v) = d’(u, v) - h(u) + h(v) ] ahol:
    • (d’(u, v)) az újrasúlyozott gráfban számított távolság,
    • (d(u, v)) az eredeti gráfban keresett távolság.


Pszeudokód

JohnsonAlgorithm(G):
    1. Adj egy új csúcsot (s) a gráfhoz, és kösd össze minden csúccsal 0 súlyú élekkel.
    2. Futtasd a Bellman-Ford algoritmust az (s)-ből:
        - Ha negatív súlyú kör található, térj vissza "HIBA".
        - Különben tárold a csúcsokhoz tartozó h értékeket.
    3. Súlyok újraszámítása:
        w'(u, v) = w(u, v) + h(u) - h(v)
    4. Távolságok számítása:
        - Minden csúcsból futtasd a Dijkstra-algoritmust az újrasúlyozott gráfban.
        - Az eredeti távolságok: d(u, v) = d'(u, v) - h(u) + h(v).
    5. Térj vissza az összes legrövidebb úttal.

Python implementáció

import heapq
import math

def bellman_ford(graph, source, num_nodes):
    distance = {node: math.inf for node in range(num_nodes)}
    distance[source] = 0

    for _ in range(num_nodes - 1):
        for u in graph:
            for v, w in graph[u]:
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w

    for u in graph:
        for v, w in graph[u]:
            if distance[u] + w < distance[v]:
                raise ValueError("Negatív súlyú kör található!")

    return distance

def dijkstra(graph, source, num_nodes):
    distance = {node: math.inf for node in range(num_nodes)}
    distance[source] = 0
    pq = [(0, source)]

    while pq:
        curr_dist, u = heapq.heappop(pq)
        if curr_dist > distance[u]:
            continue

        for v, w in graph[u]:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                heapq.heappush(pq, (distance[v], v))

    return distance

def johnson_algorithm(graph, num_nodes):
    new_graph = graph.copy()
    new_source = num_nodes

    new_graph[new_source] = [(i, 0) for i in range(num_nodes)]

    try:
        h = bellman_ford(new_graph, new_source, num_nodes + 1)
    except ValueError as e:
        return str(e)

    reweighted_graph = {}
    for u in graph:
        reweighted_graph[u] = []
        for v, w in graph[u]:
            reweighted_weight = w + h[u] - h[v]
            reweighted_graph[u].append((v, reweighted_weight))

    all_distances = {}
    for u in range(num_nodes):
        all_distances[u] = dijkstra(reweighted_graph, u, num_nodes)

        for v in all_distances[u]:
            if all_distances[u][v] < math.inf:
                all_distances[u][v] += h[v] - h[u]

    return all_distances

# Példa gráf
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
num_nodes = 4

distances = johnson_algorithm(graph, num_nodes)
print("Legrövidebb utak:")
for src, dist in distances.items():
    print(f"{src}: {dist}")

Kimenet: 

Legrövidebb utak:
0: {0: 0, 1: 3, 2: 1, 3: 4}
1: {0: inf, 1: 0, 2: inf, 3: 1}
2: {0: inf, 1: 2, 2: 0, 3: 3}
3: {0: inf, 1: inf, 2: inf, 3: 0}

Előnyök

  1. Hatékonyság ritka gráfok esetén:
    • Az algoritmus (O(V^2 V + VE)) időben fut, ami ritka gráfoknál hatékony.
  2. Negatív élhosszok kezelése:
    • A Bellman-Ford-algoritmus révén képes negatív súlyú élek kezelésére (negatív körök nélkül).
  3. Egyszerűség:
    • A Bellman-Ford és a Dijkstra algoritmusok kombinációja jól ismert és könnyen implementálható.


Hátrányok

  1. Negatív súlyú körök:
    • Az algoritmus nem működik, ha a gráf negatív súlyú köröket tartalmaz.
  2. Nagy memóriaigény:
    • Nagy gráfok esetén az összes legrövidebb út tárolása jelentős memóriát igényelhet.
  3. Tömör gráfok esetén kevésbé hatékony:
    • Tömör gráfok esetén más algoritmusok, mint a Floyd-Warshall, hatékonyabbak lehetnek.


Alkalmazások

  1. Hálózati útvonalak optimalizálása:
    • Hálózati csomópontok közötti optimális útvonalak kiszámítása.
  2. Logisztika és szállítmányozás:
    • Optimális útvonalak meghatározása szállítási rendszerekben.
  3. Rendszertervezés:
    • Az összes csúcs közötti minimális költségek kiszámítása.


Összegzés

A Johnson-algoritmus hatékony eszköz az irányított, súlyozott gráfok legrövidebb útjainak meghatározására, különösen ritka gráfok esetében. Bár negatív súlyú élekkel is működik, a negatív körök jelenléte problémát okozhat. Ez a kombinált megközelítés a Dijkstra és a Bellman-Ford algoritmusok erejét használja fel a legrövidebb utak gyors és pontos kiszámításához.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Johnson-algoritmus&oldid=3479581”