szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
shortest path problem (tsz. shortest path problems)
- (informatika) A legrövidebb út problémája (angolul: Shortest Path Problem) egy klasszikus probléma a gráfelméletben és az operációkutatásban, amelynek célja:
Megtalálni a két pont közötti minimális összköltségű (vagy legrövidebb hosszúságú) utat egy gráfban, ahol az élek súlyozottak lehetnek.
Ez a probléma a szállítás, útvonaltervezés, kommunikációs hálózatok, robotika, térinformatika (GIS) és a mesterséges intelligencia egyik alapköve.
Legyen egy gráf:
, ahol:
: csúcsok (pontok) halmaza
: élek halmaza
- Minden élhez tartozik egy súlyfüggvény:
, ami lehet távolság, idő, költség stb.
A cél: adott
(forrás) és
(cél) csúcs esetén találjuk meg az
-től
-ig vezető legkisebb súlyú utat.
3. Problémafajták
Típus
|
Leírás
|
Egy forrás – egy cél
|
Legrövidebb út két konkrét pont között
|
Egy forrás – minden cél
|
Minden más csúcs elérése a forrásból
|
Minden pont – minden pont
|
Legrövidebb út minden csúcspárra
|
Negatív élek
|
Lehetnek negatív élértékek is (de nem negatív körök!)
|
Dinamikus változatok
|
Élértékek változhatnak, új csúcsok jelennek meg
|
4. Algoritmusok a legrövidebb út keresésére
✅ 1. Dijkstra algoritmusa (pozitív élértékekre)
Leggyakoribb módszer, ha nincsenek negatív súlyú élek.
Lépései:
- Minden csúcs távolságát végtelenre állítjuk, kivéve a forrást (0).
- Minden lépésben kiválasztjuk a legkisebb távolságú csúcsot.
- Frissítjük szomszédai távolságát, ha rövidebb utat találunk.
- Addig ismételjük, míg minden csúcsot meglátogattunk.
Időkomplexitás:
prioritási sorral (pl. Fibonacci heap-pel)
✅ 2. Bellman–Ford algoritmus (negatív élekre is alkalmas)
- Működik negatív súlyú élekkel is, de nem engedi a negatív köröket.
- Többször végigmegy az éleken, és relaxálja a távolságokat.
Időkomplexitás: 
✅ 3. Floyd–Warshall algoritmus (minden csúcspárra)
- Dinamikus programozás alapú megközelítés
- Minden-minden csúcspár közötti legrövidebb utakat határoz meg
Időkomplexitás: 
✅ 4. A* algoritmus (heurisztikus, AI)
- Egy becslés segítségével gyorsabban találja meg az utat (pl. térképeken)
- Heurisztikát használ, pl. „madártávolság” a célhoz
5. Dijkstra algoritmus példája
Gráf:
A --1-- B --3-- C
| |
4 1
| |
D-------E
Élek:
- A–B (1), A–D (4), B–C (3), B–E (1), D–E (1)
Forrás: A Cél: C
Lépések:
- A: 0
- B: 1 (A–B)
- E: 2 (B–E)
- D: 3 (A–D vagy E–D)
- C: 4 (B–C)
Legrövidebb út: A → B → C Összköltség: 4
6. Python példa (Dijkstra)
import heapq
def dijkstra(graph, start):
dist = {v: float('inf') for v in graph}
dist = 0
pq =
while pq:
d, u = heapq.heappop(pq)
for v, w in graph:
if dist > d + w:
dist = d + w
heapq.heappush(pq, (dist, v))
return dist
# Példagráf (szomszédsági lista)
graph = {
'A': ,
'B': ,
'C': ,
'D': ,
'E':
}
print(dijkstra(graph, 'A'))
# Kimenet: {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 2}
7. Negatív súlyú körök
A negatív kör egy olyan hurok a gráfban, amelynek teljes súlya negatív. Ha ilyet találunk, akkor a legrövidebb út nem létezik (a súly korlát nélkül csökkenthető).
A Bellman–Ford képes észlelni a negatív köröket.
8. Alkalmazások
Terület
|
Alkalmazás
|
Navigáció
|
GPS útvonaltervezés
|
Távközlés
|
Adatcsomag útvonalának meghatározása
|
Logisztika
|
Legolcsóbb szállítási útvonal
|
Szociológia
|
Kapcsolati hálók legkisebb távolságai
|
Mesterséges intelligencia
|
Játékállapotok közötti legrövidebb lépéssorozat
|
9. További változatok
- Legkisebb késleltetésű út
- Költség és idő kombinált optimalizálása
- Több kritériumos útkeresés
- Korlátozott súlyú utak (pl. max 3 átszállás)
10. Összefoglalás
A legrövidebb út problémája az egyik legfontosabb grafalgoritmus:
- Általános célja: két csúcs közötti minimális súlyú út megtalálása
- Különböző algoritmusok léteznek a feladattól függően (Dijkstra, Bellman–Ford, Floyd–Warshall, A*)
- Széleskörűen alkalmazható a valós életben és számítástechnikában
- Hatékony megoldások állnak rendelkezésre nagy gráfokra is