1. Алгоритмы: Дейкстры (короткий путь); Прима, Краскала (дешёвый путь)
Алгоритм Дейкстры (поиск кратчайшего пути от вершины 1):
Начальная вершина 1:
1 → 2: 2
1 → 3: 4
1 → 4: 8
Выбираем вершину 2 (минимальное расстояние):
2 → 3: 6 (через 2)
2 → 5: 9 (через 2)
Выбираем вершину 3:
3 → 4: 8 (через 3)
3 → 5: 11 (через 3)
Выбираем вершину 4:
4 → 5: 13 (через 4)
Алгоритмы Прима и Краскала (построение минимального остовного дерева):
Ребра в минимальном остовном дереве по Приму: 1-2, 1-3, 3-4, 2-5.
Ребра в минимальном остовном дереве по Краскалу: 1-2, 1-3, 4-3, 2-5.
2. Алгоритмы Хаффмана и Фано
Необходимо составить коды Хаффмана и Фано для заданных символов и частот их встречаемости. (В данной задаче конкретные символы и частоты не указаны, поэтому пример оставим без решения).
![](https://otvet.imgsmail.ru/download/19765033_91b07f1b481a8e48950087ad86915818_800.png)
Метод Кондорсе:
Определяем победителя попарных сравнений (данные для конкретного сравнения не указаны, но решается аналогично методу Борда с попарными сравнениями).
4. Транспортные задачи: северо-западный угол, жадный алгоритм, алгоритм Фогеля
Метод северо-западного угла:
A1 → B1: 7
A1 → B2: 5 (остаток 10)
A2 → B2: 3 (остаток 17)
A2 → B3: 20 (остаток 20)
A3 → B2: 2 (остаток 15)
A3 → B3: 18 (остаток 15)
Жадный алгоритм:
Выбираем минимальную стоимость поставки и распределяем её на основе запасов и заявок.
Алгоритм Фогеля:
Вычисляем разности между двумя наименьшими затратами в каждой строке и столбце, выбираем наибольшую разность и осуществляем поставку по наименьшей стоимости.