| 7 | | 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 megenegedett 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). |
| | 7 | 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). |
