Проблема заключается в следующем:
Вам дан взвешенный график, состоящий из h домов, s магазинов и r дорог. Дома и магазины - это вершины, дороги - это ребра разной длины. Для этого вы должны поддерживать кратчайшие пути от любого дома до любого магазина и длину этих путей. Решение должно быть эффективным. Дороги могут быть выведены из строя (удаление этого ребра), а магазины могут быть закрыты (удаление вершины).
Какие динамические c графовые алгоритмы вы бы использовали для этой задачи? Я смотрел на Even-Shiloach, но не уверен, что полностью понимаю его.
Любая помощь очень, очень ценится. Спасибо!