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

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

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


algorithm path-finding shortest-path graph-theory
person parsa rastegari    schedule 17.12.2010    source источник
comment
Что такое? Количество ребер или вершин?   -  person Enrique    schedule 17.12.2010
comment
Ваша формулировка может быть улучшена. Матрица - дельта, элемент матрицы - дельта (i, j).   -  person Chris Hopman    schedule 17.12.2010
comment
Интересный вопрос. Я почти уверен, что нет решения быстрее, чем повторный запуск Floyd-Warshall, что составляет O (n ^ 3), но я не могу этого доказать.   -  person Nick Johnson    schedule 17.12.2010

Ответы (3)


arrow_upward
6
arrow_downward

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

Следовательно, алгоритм O (n ^ 2) для обновления всей матрицы является тривиальным, как и тот, который имеет дело с неориентированными графами.

person Chris Hopman    schedule 17.12.2010
comment
Если я серьезно не понимаю вопрос, мы не знаем компонентов кратчайшего пути. Чтобы обновить дельты путей, в которых W 'является компонентом, нам необходимо их знать. И если мы не сможем сделать это за постоянное время, мы превысим наш предел. - person Robert; 17.12.2010
comment
Я действительно не понял, что вы сказали. У нас есть только дельта-матрица, содержащая только значения, обозначающие длину кратчайшего пути. Откуда вы могли знать, что ребро E было ранее на кратчайшем пути от i до j или нет? у тебя просто есть номер. - person parsa rastegari; 17.12.2010
comment
Позвольте мне еще раз прояснить вопрос: все, что у нас есть, - это график и его дельта-матрица. Дельта-матрица содержит только значение кратчайшего пути. теперь мы хотим обновить матрицу дельты в соответствии с изменением графика: уменьшенным весом ребра. как обновить его за O (n ^ 2)? - person parsa rastegari; 17.12.2010
comment
какие-либо предложения? я перефразировал свой вопрос и уточнил его. см. выше. - person parsa rastegari; 17.12.2010
comment
Да, я знаю. Прочтите то, что я сказал еще раз. Вам не нужно знать, содержал ли старый путь ребро. Кратчайший путь от a до b, содержащий ребро от i до j, имеет длину delta(a, i) + edge(i, j) + delta(j, b). - person Chris Hopman; 17.12.2010
comment
@Chris - Как узнать, что он такой же, как старый, или в нем есть край? Имеет смысл, что сумма будет меньше, если она содержит ребро, но вы говорите, что это единственный случай, когда она будет меньше? - person Robert; 17.12.2010
comment
@ Роберт. Ты явно не понял. Меня не волнует, содержал ли старый кратчайший край ребро или нет. Меня интересует только длина старого кратчайшего пути и длина нового кратчайшего пути, содержащего измененный край. Если новый кратчайший путь не содержит ребра, то он явно такой же, как и старый кратчайший путь. - person Chris Hopman; 17.12.2010
comment
Я только что понял, что поменял местами i, j и a, b при вычислении длины, но не думаю, что это вызывает путаницу. - person Chris Hopman; 17.12.2010
comment
@ Роберт: Похоже, Крис прав. Нам не нужно знать, было ли на предыдущем кратчайшем пути ребро E или нет. мы вычисляем новый кратчайший путь, и если он имеет меньшее значение, чем предыдущая дельта (i, j), мы обновляем его новым. @Chris: не будет ли проблем с использованием delta (a, i) и delta (j, b)? Я сам сейчас не нахожу ничего плохого в вашем решении, но я думаю, что проблема должна быть более сложной, чем это;) все ли вы согласны с тем, что приведенное выше решение Криса правильное? (Еще раз подчеркивая, что вышеупомянутый подход не требует знаний о предыдущем дорожка) - person parsa rastegari; 17.12.2010
comment
@Chris - Одному из нас чего-то не хватает, и я подозреваю, что это я. Но теперь мне кажется, я понимаю, о чем вы говорите. Компоненты кратчайшего пути a- ›z сами по себе являются кратчайшими путями. Это означает, что _1 _ + _ 2 _ + _ 3_ будет короче старого a->z, если i->j был частью исходного пути. В этом случае обновите. Мне это кажется правильным, но я явно не в состоянии это проверить. - person Robert; 17.12.2010
comment
@parsa нет, проблем не будет. Ни один из этих путей не будет содержать ребра, вес которого изменился. Это потому, что кратчайший путь от x до y не будет содержать ребро, выходящее из y или входящее в x. - person Chris Hopman; 17.12.2010
comment
@Chris: в каком порядке вы будете обновлять дельту? что произойдет, если, например, delta (1,2) обновляется, и вам нужно его значение для вычисления delta (2,3)? если вы понимаете, о чем я? звучит как более сложный. - person parsa rastegari; 17.12.2010
comment
@Robert - Да, составляющие кратчайшего пути - это кратчайшие пути. Это означает, что, как правило, если кратчайший путь от i до j содержит a, а затем b, его длина равна (i->a) + (a->b) + (b->j). В случае, когда кратчайший путь содержит ребро от a до b, эта длина равна (i->a) + edge(a,b) + (b->j). Обратите внимание, что новый кратчайший путь может быть короче старого, даже если старый путь не содержал укороченного ребра. Это не проблема. - person Chris Hopman; 17.12.2010
comment
@Parsa Фактически вы не будете изменять значения для delta(x,a) или delta(b,x). Это потому, что кратчайший путь, заканчивающийся на a, не будет содержать ребра, выходящего из a. И аналогично для такого пути, начинающегося с b. - person Chris Hopman; 17.12.2010
comment
@Chris: Я пропустил ваш комментарий относительно того факта, что ни один из этих путей не будет содержать ребро, вес которого изменился. Что ж, согласен. определенно нам просто нужны delta (a, i) и delta (j, b), которые нельзя изменить, так как они никогда не могут содержать (i, j) сами. Что ж, вроде проблема решена :), спасибо большое. Но я все еще немного волнуюсь, возникнут ли проблемы с этим решением или нет. где-то мне нужен ответ, и я знаю, что вопросы должны быть сложными;), я сам не могу понять никаких проблем с указанным выше решением. Хорошо! - person parsa rastegari; 17.12.2010
comment
Это правильно. И это очевидно в ретроспективе, как и все элегантные решения. Это также ключевая идея floyd-warshall, поэтому мне неловко, что я не понял, как применить ее здесь. Молодец! - person Nick Johnson; 17.12.2010

arrow_upward
0
arrow_downward

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 n n. Википедия, наверное, не актуальна;)

person excalibur1491    schedule 22.03.2015

arrow_upward
-1
arrow_downward

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

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

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

person Robert    schedule 17.12.2010
comment
Дейкстра дает кратчайшие пути из одного источника. - person Sanjit Saluja; 17.12.2010
comment
Да, можно использовать Dijkstra для обновления одной строки матрицы (и одного столбца, если граф неориентированный) менее чем за O (n ^ 2). Но обновить всю матрицу было бы хуже, чем за O (n ^ 2). - person Chris Hopman; 17.12.2010
comment
Что ж, проблема не в кратчайшем пути из одного источника, чтобы использовать dijkstra и получить O (n ^ 2). мы хотим вычислить кратчайшие пути из ВСЕХ пар (сохраненные в delta (i, j)), и лучший способ вычислить всю дельту - O (n ^ 3) {указано в CLRS}. Здесь мы хотим обновить дельту (не пересчитывать ее полностью СНОВА) в соответствии с изменением одного ребра. - person parsa rastegari; 17.12.2010
comment
@Robert Выполнение чего-то, что (примерно) n log n, n ^ 2 раза, стоит O (n ^ 3 log n), а не O (n ^ 2). В противном случае вы могли бы сделать что-то, что стоит O (n!), N раз за O (n)! - person Nick Johnson; 17.12.2010
comment
@sanjit, @chris - совершенно точно. Я отредактировал свой вопрос, пока вы писали, и с тех пор обновил его снова. @parsa - Согласен. Но без знания компонентов кратчайшего пути невозможно узнать (что я могу придумать) узнать, какие компоненты матрицы должны быть обновлены. Если бы вы это сделали, это было бы простое вычитание. - person Robert; 17.12.2010
comment
@ Роберт: O (E + VlogV) * O (V ^ 2) будет хуже, чем O (V ^ 2), который мы хотели. это правильно ? V = количество вершин = n - person parsa rastegari; 17.12.2010
comment
@Nick - да, смотри мою правку около 10 минут назад. Я фейспалмал примерно через 20 секунд после публикации. - person Robert; 17.12.2010
comment
@Robert: Нам дана как G (график), так и матрица Delta. Итак, у вас есть знания о графике. - person parsa rastegari; 17.12.2010
comment
@parsa - Согласен. Учтите, что итерация по матрице сама по себе составляет O (n ^ 2). Таким образом, обновление пары необходимо производить в постоянное время. Это было бы легко, если бы у вас был список ребер на этом кратчайшем пути? - можно просто вычесть разницу. Но мы этого не делаем. Поэтому нам нужно снова найти кратчайший путь, чтобы узнать новый вес - или нам нужно разумно игнорировать большие части матрицы. Может быть, я что-то упускаю, но, как я отмечал выше, это практически невозможно сделать в n ^ 2. - person Robert; 17.12.2010
comment
какие-либо предложения? я перефразировал свой вопрос и уточнил его. см. выше. - person parsa rastegari; 17.12.2010