Coursera: algs4partII-001. Неделя 2. Minimum Spanning Trees и Shortest Paths

[svetasmirnova]

Часть 1. Minimum Spanning Trees.

Всё очень просто.

1. Kruskal's algorithm - проходить edges в порядке возрастания и добавлять, если не возникает циклов.
2. Prim's algorithm - всё тоже самое, но плясать от построенного дерева.

Единственная сложность в задании - не ошибиться в записи промежуточных ответов. К счастью, графическое представление графов сделано в ASCII, поэтому я просто копировала в текстовый файл и помечала пройденный edge крестиками буквой Х.

Часть 2. Shortest Paths.

Здесь для записи промежуточных ответов было удобно пользоваться LibreOffice Calc.

1. Dijkstra's algorithm - всё просто, relax a vertex, выбираем vertex с наименьшей дистанцией, relax его и так до победного.
2. Topological order - аналогично предыдущему, но vertex-ы выбираем в указанном порядке.
3. Bellman-Ford algorithm - а вот с ним я помучалась. Почему-то не сразу сообразила в каком порядке relax vertex-ы. А проходятся они на каждом шаге от первого до последнего. Вкратце:
   
   1. Шаг 1. Все vertex-ы - infinity, кроме того, от которого считаем дистанцию. Он - 0. Relax первый vertex. Предположим, это D. Значит, A, B и С мы уже прошли. Их relax на этом шаге больше не нужно. А если D "открыл" последующие, скажем, E и F, их нужно relax по порядку. Причём, если D "открыл" E, а сумма расстояний от D-F-E меньше расстояния от D до E, менять ничего на этом шаге не нужно. А вот если расстояние D-E-F меньше расстояния D-F - значение для F изменить нужно.
   2. Шаг 2. Проходим все vertex-ы, открытые на предыдущем шаге, в порядке возрастания. Опять-таки, никаких возвратов обратно.
   3. Шаг 3. Аналогично шагу 2.