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).
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.
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.
import heapq
import math
def bellman_ford(graph, source, num_nodes):
distance = {node: math.inf for node in range(num_nodes)}
distance = 0
for _ in range(num_nodes - 1):
for u in graph:
for v, w in graph:
if distance + w < distance:
distance = distance + w
for u in graph:
for v, w in graph:
if distance + w < distance:
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 = 0
pq =
while pq:
curr_dist, u = heapq.heappop(pq)
if curr_dist > distance:
continue
for v, w in graph:
if distance + w < distance:
distance = distance + w
heapq.heappush(pq, (distance, v))
return distance
def johnson_algorithm(graph, num_nodes):
new_graph = graph.copy()
new_source = num_nodes
new_graph =
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 =
for v, w in graph:
reweighted_weight = w + h - h
reweighted_graph.append((v, reweighted_weight))
all_distances = {}
for u in range(num_nodes):
all_distances = dijkstra(reweighted_graph, u, num_nodes)
for v in all_distances:
if all_distances < math.inf:
all_distances += h - h
return all_distances
# Példa gráf
graph = {
0: ,
1: ,
2: ,
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}
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.