---

Задание: Алгоритмы поиска кратчайшего пути во взвешенном графе
Общая часть
Студенты выполняют задание по вариантам. Каждый вариант предполагает 
реализацию одного алгоритма поиска кратчайшего пути во взвешенном графе, 
отображение графа в виде диаграммы Mermaid, описание псевдокода с 
обозначением переменных и измерение времени выполнения на заданном 
графе.
Задание 1. Алгоритм Дейкстры
Постановка задачи
Дан взвешенный ориентированный граф без рёбер с отрицательным весом. 
Требуется найти кратчайшие расстояния от заданной начальной вершины до 
всех остальных вершин графа.
Граф для выполнения задания
Вершины: A, B, C, D, E, F.
Начальная вершина: A.
Псевдокод
Обозначения переменных:
G — граф, представленный списком смежности;
s — начальная вершина;
V — множество вершин графа;
dist[v] — текущее кратчайшее расстояние от s до вершины v;
visited[v] — логический флаг, указывающий, обработана ли вершина v;
pq — очередь с приоритетом, хранящая пары (расстояние, вершина);Алгоритм Дейкстры (G, s)
1. Для каждой вершины v из V:
2.     dist[v] := бесконечность
3.     visited[v] := ложь
4. dist[s] := 0
5. pq := пустая очередь с приоритетом
6. добавить в pq пару (0, s)
7. Пока pq не пуста:
8.     (d, u) := извлечь из pq элемент с минимальным d
9.     Если visited[u] = истина:
10.продолжить
11.    visited[u] := истина
12.Для каждого ребра (u, v) с весом w в G:
13.        Если dist[u] + w < dist[v]:
14.            dist[v] := dist[u] + w
15.            добавить в pq пару (dist[v], v)
16. Вернуть массив dist
Требуется измерить
Время выполнения алгоритма на заданном графе. Замер производится с 
использованием системного таймера языка программирования. Результат 
выводится в секундах или миллисекундах с указанием единицы измерения
Задание 2. Алгоритм Беллмана — Форда
Постановка задачи
Дан взвешенный ориентированный граф, допускающий наличие рёбер с 
отрицательным весом. Требуется найти кратчайшие расстояния от заданной 
начальной вершины до всех остальных вершин графа, а также определить 
наличие цикла отрицательного веса, достижимого из начальной вершины.
Граф для выполнения задания
u — текущая извлекаемая вершина;
w — вес ребра (u, v);
d — извлечённое расстояние.Вершины: A, B, C, D, E, F.
Начальная вершина: A.
Псевдокод
Обозначения переменных:
G — граф, представленный списком рёбер;
s — начальная вершина;
V — множество вершин графа;
E — множество рёбер графа;
dist[v] — текущее кратчайшее расстояние от s до вершины v;
u — начало ребра;
v — конец ребра;
w — вес ребра (u, v);
i — счётчик итераций внешнего цикла;
n — количество вершин графа.
Алгоритм Беллмана — Форда (G, s)
1. Для каждой вершины v из V:
2.     dist[v] := бесконечность
3. dist[s] := 0
4. n := количество вершин в V
5. Для i от 1 до n - 1:
6.Для каждого ребра (u, v) с весом w в E:
7.         Если dist[u] не равно бесконечности и dist[u] + w < dist[v]:
8.             dist[v] := dist[u] + w
9. Для каждого ребра (u, v) с весом w в E:
10.    Если dist[u] не равно бесконечности и dist[u] + w < dist[v]:
11.Вернуть сообщение "Граф содержит цикл отрицательного веса"
12. Вернуть массив dist
Требуется измеритьВремя выполнения алгоритма на заданном графе. Замер производится с 
использованием системного таймера языка программирования. Результат 
выводится в секундах или миллисекундах с указанием единицы измерения.