Рубрики

Некоторые интересные вопросы кратчайшего пути | Комплект 1

Вопрос 1: Дан ориентированный взвешенный граф. Вам также дается кратчайший путь от исходной вершины 's' до конечной вершины 't'. Если вес каждого ребра увеличивается на 10 единиц, остается ли кратчайший путь неизменным на измененном графике?
Кратчайший путь может измениться. Причина в том, что может быть разное количество ребер на разных путях от s до t. Например, пусть кратчайший путь имеет вес 15 и имеет 5 ребер. Пусть будет еще один путь с 2 ребрами и общим весом 25. Вес самого короткого пути увеличится на 5 * 10 и станет 15 + 50. Вес другого пути увеличится на 2 * 10 и станет 25 + 20. Таким образом, кратчайший путь меняется на другой путь с весом 45.

Вопрос 2: Это похоже на вопрос выше. Меняется ли кратчайший путь, когда веса всех ребер умножаются на 10?
Если мы умножим все веса ребер на 10, кратчайший путь не изменится. Причина проста: веса всех путей от s до t умножаются на одинаковую величину. Количество ребер на пути не имеет значения. Это как смена единицы веса.

Вопрос 3: Для ориентированного графа, в котором вес каждого ребра равен 1 или 2, найдите кратчайший путь от заданной исходной вершины 's' до заданной конечной вершины 't'. Ожидаемая сложность времени O (V + E).
Если мы применяем алгоритм кратчайшего пути Дейкстры , мы можем получить кратчайший путь за время O (E + VLogV). Как это сделать за время O (V + E)? Идея состоит в том, чтобы использовать BFS . Одним из важных замечаний о BFS является то, что путь, используемый в BFS, всегда имеет наименьшее количество ребер между любыми двумя вершинами. Поэтому, если все ребра имеют одинаковый вес, мы можем использовать BFS, чтобы найти кратчайший путь. Для этой задачи мы можем изменить график и разбить все ребра веса 2 на два ребра веса 1 каждый. В модифицированном графе мы можем использовать BFS, чтобы найти кратчайший путь. Как этот подход O (V + E)? В худшем случае все ребра имеют вес 2, и нам нужно выполнить O (E) операций, чтобы разбить все ребра, поэтому временная сложность становится O (E) + O (V + E), которая равна O (V + E).

Вопрос 4:   Учитывая заданный ациклический взвешенный граф, как найти кратчайший путь от источника s к месту назначения t за O (V + E) времени?
См .: Кратчайший путь в направленном ациклическом графе

Дополнительные вопросы Смотрите следующие ссылки для получения дополнительных вопросов.
http://algs4.cs.princeton.edu/44sp/
http://espressocode.top/algorithms-gq/graph-shortest-paths-gq/

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Некоторые интересные вопросы кратчайшего пути | Комплект 1

0.00 (0%) 0 votes