COIN-OR::LEMON - Graph Library

Version 2 (modified by Peter Kovacs, 10 years ago) (diff)

--

Negatív körök keresése

Hatékony algoritmusok implementálása annak eldöntésére, hogy van-e negatív költségű irányított kör egy gráfban.

Háttér

A legrövidebb utak kereséséhez szorosan kapcsolódó probléma annak eldöntése, hogy létezik-e negatív összköltségű irányított kör egy élsúlyozott gráfban. Ha ilyen kör nem létezik, akkor bármely két pont között létezik minimális költségű séta, amelyet a Bellman-Ford-algoritmussal meg is kereshetünk. Más megközelítésben azt mondhatjuk, hogy ilyenkor létezik megengedett potenciálfüggvény: minden u csúcshoz hozzárendelhetünk egy d(u) potenciált, amelyre teljesül, hogy minden (u, v) élen a c(u,v) + d(u) - d(v) redukált költség nemnegatív (vagyis d(u) + c(u,v) >= d(v)). Egy ilyen potenciálfüggvény ismeretében a legröviebb utak keresését hatékonyan tudjuk megoldani Dijkstra algoritmusával (a redukált költségeket használva).

Egy érdekes és fontos feladat tehát annak eldöntése, hogy egy irányított, élsúlyozott gráf tartalmaz-e negatív kört. Olyan algoritmusokat keresünk, amelyek megadnak egy negatív kört, ha ilyen létezik, egyébként pedig egy megengedett potenciálfüggvényt. A klasszikus Bellman-Ford algoritmus alkalmas ezen probléma megoldására, de a gyakorlatban sokszor nem elég hatékony. Ugyanakkor számos hasonló, de a gyakorlatban jobban teljesítő algoritmus is született.

Az alábbi cikk részletesen elemzi és összehasonlítja a különböző módszereket:

Feladat

A feladat a fenti probléma megoldására született leghatékonyabb algoritmusok implementálása és összehasonlító elemzése különböző gráfokon.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Előfeltételek

  • C++ programozási nyelv ismerete
  • alapvető gráfelméleti ismeretek
  • angol nyelvismeret