188 Глава 6. Алгоритмы на графах
щаетесь к ребру несколько раз, то всякий раз его нужно учитывать заново).
2)Измените приведенный в последнем разделе алгоритм таким образом, чтобы он эффективно определял кратчайший путь из данной вершины графа во все остальные его вершины, а не только в одну указанную.
3)Выполните анализ алгоритма поиска кратчайшего пути, подсчитав, сколько раз рассматривается каждое ребро при добавлении вершин к кайме, при обновлении списка ребер, ведущих в кайму, и при перенесении вершины из каймы в МОД.
4)Докажите, что обход по уровням строит кратчайшие пути в графе без весов.
5)Может ли так случиться, что порядок добавления ребер к дереву кратчайшего пути совпадает с порядком их появления при обходе дерева по уровням? Или так происходит всегда? Или такое вообще невозможно? Обоснуйте свой ответ.
