Please read the new rule regarding the restriction on the use of AI tools. ×

Дейкстра с потенциалами(mincost maxflow)

Revision ru1, by skrydg, 2015-11-21 15:28:02

Изначально потенциалы равны кратчайшим расстояниям.

Вопрос 1: Как обновлять потенциалы?

Вопрос 2: Как доказывать, что при таком обновлении потенциалов не возникнет ребер отрицательной стоимости?

Говорят, что надо к старым потенциалам надо просто прибавить новое расстояние. Верно ли это?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian skrydg 2015-11-21 15:28:02 344 Первая редакция (опубликовано)