shortest path problem

Üdvözlöm, Ön a shortest path problem szó jelentését keresi. A DICTIOUS-ban nem csak a shortest path problem 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 shortest path problem szót egyes és többes számban mondani. Minden, amit a shortest path problem szóról tudni kell, itt található. A shortest path problem szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Ashortest path problem é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)

  1. (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.



2. A probléma formalizálása

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:
  1. Minden csúcs távolságát végtelenre állítjuk, kivéve a forrást (0).
  2. Minden lépésben kiválasztjuk a legkisebb távolságú csúcsot.
  3. Frissítjük szomszédai távolságát, ha rövidebb utat találunk.
  4. 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