I detta dokument studerar vi dynamiska kortaste stigproblem, som är att bestämma en kortaste väg från en specificerad källa nod till varje annan nod i nätverket där bågens restider förändras dynamiskt. Vi överväger två problem: den minsta tid promenad problem (som är att hitta en promenad med den minsta restiden) och den lägsta kostnaden promenad problem (som är att hitta en promenad med den lägsta resekostnaden). Minimitiden gång problemet är känt för att vara polynomiskt lösbar för en klass av nätverk som kallas FIFO-nätverk. Detta dokument ger följande bidrag: (i) vi visar att den minsta kostnad gång problemet är ett NP-komplett problem; (ii) vi utvecklar en pseudopolynom-tid algoritm för att lösa den minsta kostnad gång problem (för heltal restider); och (iii) vi utvecklar en polynom-tid algoritm för minimal tid promenad problem uppstår i vägnät med trafikljus.
Ahuja i REF visar att det dynamiska kortaste stigproblemet, där restiderna förändras dynamiskt, också är ett NP-komplett problem.
Dynamic Shortest Paths Minimizing Travel Times and Costs
{'venue': 'Networks', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}