Срочно решить задачи по информатике

Алгоритмы: Дейкстра (короткий путь); Прима, Краскала (дешевый путь)

Граф с вершинами и весами рёбер:

 1 - 2: 2 
1 - 3: 4 
2 - 3: 4 
2 - 5: 7 
3 - 4: 8 
3 - 5: 5 
4 - 5: 5 
 

Алгоритм Дейкстры для поиска кратчайшего пути от вершины 1 до остальных вершин:

Начальная вершина: 1, метки: [0, ∞, ∞, ∞, ∞]
Обновляем метки: 1->2 (2), 1->3 (4)
Выбираем минимальную метку: 2
Обновляем метки: 2->3 (4+4=8, не обновляем, т.к. 4<8), 2->5 (2+7=9)
Выбираем минимальную метку: 3
Обновляем метки: 3->4 (4+8=12), 3->5 (4+5=9, не обновляем, т.к. 9=9)
Выбираем минимальную метку: 5
Обновляем метки: 5->4 (9+5=14, не обновляем, т.к. 12<14)
Выбираем минимальную метку: 4
Конечный результат: кратчайшие пути от 1 до всех остальных: [0, 2, 4, 12, 9]
Алгоритмы Прима и Краскала для поиска минимального остовного дерева:

Алгоритм Прима:

Начальная вершина: 1
Выбираем ребро с минимальным весом: 1-2 (2)
Выбираем ребро с минимальным весом: 1-3 (4)
Выбираем ребро с минимальным весом: 3-5 (5)
Выбираем ребро с минимальным весом: 5-4 (5)
Итоговое дерево: рёбра {1-2, 1-3, 3-5, 5-4}
Алгоритм Краскала:

Выбираем ребро с минимальным весом: 1-2 (2)
Выбираем ребро с минимальным весом: 1-3 (4)
Выбираем ребро с минимальным весом: 3-5 (5)
Выбираем ребро с минимальным весом: 5-4 (5)
Итоговое дерево: рёбра {1-2, 1-3, 3-5, 5-4}