shortest path problem

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.

Legyen egy gráf:

• ${\textstyle G=(V,E)}$, ahol:
  • ${\textstyle V}$: csúcsok (pontok) halmaza
  • ${\textstyle E}$: élek halmaza
• Minden élhez tartozik egy súlyfüggvény: ${\textstyle w:E\rightarrow \mathbb {R} }$, ami lehet távolság, idő, költség stb.

A cél: adott ${\textstyle s}$ (forrás) és ${\textstyle t}$ (cél) csúcs esetén találjuk meg az ${\textstyle s}$-től ${\textstyle t}$-ig vezető legkisebb súlyú utat.

Leggyakoribb módszer, ha nincsenek negatív súlyú élek.

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.

• ${\textstyle O((V+E)\log V)}$ prioritási sorral (pl. Fibonacci heap-pel)

• 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.

• Dinamikus programozás alapú megközelítés
• Minden-minden csúcspár közötti legrövidebb utakat határoz meg

• 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

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

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}

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.

• 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)

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

• shortest path problem - Szótár.net (en-hu)
• shortest path problem - Sztaki (en-hu)
• shortest path problem - Merriam–Webster
• shortest path problem - Cambridge
• shortest path problem - WordNet
• shortest path problem - Яндекс (en-ru)
• shortest path problem - Google (en-hu)
• shortest path problem - Wikidata
• shortest path problem - Wikipédia (angol)