Найти кратчайший путь и его длину от вершины s=x1 до вершины t=x6 в графе g с использованием алгоритма Дейкстры

Тема: Алгоритм Дейкстры для нахождения кратчайшего и самого длинного пути в графе
Инструкция: Алгоритм Дейкстры - это алгоритм для нахождения кратчайшего пути между вершинами во взвешенном графе. Он работает следующим образом:
1. Создайте список расстояний, где для каждой вершины установите бесконечное расстояние, кроме начальной вершины, для которой расстояние равно 0.
2. Создайте список посещенных вершин. Начинаем с пустого списка.
3. Найдите вершину из списка расстояний с наименьшим значением и пометьте ее как текущую вершину.
4. Рассмотрите всех соседей текущей вершины и обновите их расстояния, если сумма расстояния от начальной вершины до текущей вершины и вес ребра между текущей вершиной и ее соседом меньше, чем текущее расстояние для соседа.
5. Повторите шаги 3 и 4 до тех пор, пока все вершины не будут посещены.
6. Теперь у нас есть список расстояний до каждой вершины. Чтобы найти кратчайший путь от вершины s до вершины t, мы можем использовать список родителей, который будет хранить информацию о предыдущей вершине для каждой вершины.
7. Чтобы найти самый длинный путь и его длину между вершинами s и t, мы можем использовать тот же алгоритм Дейкстры, но поменять условие для обновления расстояний на "больше", а не на "меньше".

Демонстрация:
Если у нас есть граф g с матрицей весов ω следующего вида:

    | 1  2  3  4  5  6

_____________________

1 | 0  5  0  0  0  7

2 | 5  0  3  0  0  0

3 | 0  3  0  2  0  0

4 | 0  0  2  0  1  0

5 | 0  0  0  1  0  4

6 | 7  0  0  0  4  0

Тогда кратчайший путь от вершины s=x1 до вершины t=x6 будет иметь длину 7, а самый длинный путь и его длина между теми же вершинами будет выглядеть следующим образом: (x1, x2, x3, x4, x5, x6) с длиной 13.

Совет: Для лучшего понимания алгоритма Дейкстры, рассмотрите его шаги на примерах с небольшими графами и создайте визуальное представление графов и путей для практики.

Дополнительное задание: Найдите кратчайший путь и его длину от вершины s=x1 до вершины t=x4 в графе g с использованием алгоритма Дейкстры, используя заданную матрицу весов ω. Затем найдите самый длинный путь и его длину между теми же вершинами.

    | 1  2  3  4 

_________________

1 | 0  3  2  0

2 | 3  0  0  4

3 | 2  0  0  1

4 | 0  4  1  0