Обновление матрицы кратчайших путей при уменьшении веса одного ребра

Question

Нам дан взвешенный граф G и дельта матрицы его кратчайшего пути.Таким образом, дельта (i, j) обозначает вес кратчайшего пути от i до j (i и j - две вершины графа).изначально задана дельта, содержащая значение кратчайших путей.Внезапно вес ребра E уменьшается от W до W '.Как обновить дельту (i, j) в O (n ^ 2)?(n = количество вершин графа) Проблема НЕ в том, чтобы снова вычислять кратчайшие пути для всех пар, что имеет наилучшую O (n ^ 3) сложность.проблема в ОБНОВЛЕНИИ дельты, так что нам не нужно повторно вычислять кратчайшие пути для всех пар.

Более подробно: все, что у нас есть, это граф и его дельта-матрица.дельта-матрица содержит только значение кратчайшего пути.Теперь мы хотим обновить дельта-матрицу в соответствии с изменением графика: уменьшен вес ребра.как обновить его в O (n ^ 2)?

Answer 1

Если у ребра E от узла a до узла b его вес уменьшился, то мы можем обновить кратчайший путь от узла i до узла j за постоянное время. Новый кратчайший путь от i до j либо совпадает со старым, либо содержит ребро от a до b. Если он содержит ребро от a до b, то его длина равна delta(i, a) + edge(a,b) + delta(b, j).

Исходя из этого, алгоритм O (n ^ 2) для обновления всей матрицы является тривиальным, как и алгоритм, имеющий дело с ненаправленными графами.

Answer 2

http://dl.acm.org/citation.cfm?doid=1039488.1039492 http://dl.acm.org.ezp.lib.unimelb.edu.au/citation.cfm?doid=1039488.1039492

Хотя оба они рассматривают увеличение и уменьшение.Увеличение сделает это сложнее.На первом, однако, стр. 973, раздел 3, они объясняют, как сделать только уменьшение в n * n.

И нет, динамические все короткие пары пары могут быть сделаны менее чем за n п п.Википедия не в курсе, я думаю;)

Answer 3

Читайте об алгоритме Дейкстры.Это то, как вы решаете эти проблемы кратчайшего пути и в любом случае выполняете меньше, чем O (n ^ 2).

EDIT Здесь есть некоторые тонкости.Похоже, вам предоставлен кратчайший путь от любого i до любого j на графике, и похоже, что вам нужно обновить всю матрицу.Итерации по этой матрице - это n ^ 2, потому что матрица - это каждый узел каждого другого, или n * n или n ^ 2.Простое повторное выполнение алгоритма Дейкстры для каждой записи в дельта-матрице не изменит этот класс производительности, поскольку n ^ 2 больше, чем производительность Дейкстры O (| E | + | V | log | V |).Я правильно читаю или я неправильно помню big-O?

РЕДАКТИРОВАТЬ, РЕДАКТИРОВАТЬ Похоже, я неправильно помню big-O.Итерации по матрице были бы n ^ 2, и Дейкстры на каждом из них были бы дополнительными издержками.Я не вижу, как это сделать в общем случае, не выясняя, какие именно пути W 'включены в ... это, кажется, подразумевает, что каждая пара должна быть проверена.Поэтому вам нужно либо обновлять каждую пару в постоянное время, либо избегать проверки значимых частей массива.