В настоящее время я изучаю кратчайшие пути в ориентированных графах.Существует множество эффективных алгоритмов для поиска кратчайшего пути в сети, например, dijkstra или bellman-ford.Но что, если график является динамическим?Говоря динамически, я имею в виду, что мы можем вставить ребра во время выполнения программы.Я пытаюсь найти эффективный алгоритм для обновления кратчайших путей от вершины v до любой другой вершины u после вставки ребра e без необходимости повторного запуска алгоритма кратчайшего пути в новом графе.Как я могу это сделать?Я обсудил с моим профессором подход, данный в этом вопросе Ссылка .Первоначально он запускает Floyd Warshall на исходном графикеЗатем, когда ребро добавляется между вершиной u и вершиной v, мы делаем следующее: Для каждой пары узлов x и y , проверьте, если d (x, u)+ c (u, v) + d (v, y), это можно сделать в O (n ^ 2) , так как вы сравниваете каждую пару узлов.// d (x, y) - это расстояние между вершиной x и вершиной y, вычисленное изначально алгоритмом Флойда Варшалла.
Я сомневаюсь, что мы можем оптимизировать описанный выше шаг, чтобы нам не пришлось проверятьдля всех пар?Можем ли мы сделать лучше или нет?Если да, какой подход?И если нет, что является доказательством того, что мы должны проверять все пары?
Я рисую некоторые графики и интуитивно чувствую, что мы должны проверить все пары, и мы не можем добиться большего успеха, но все же любое доказательство будет полезно.