Описание графа с помощью матрицы смежности

Матрица смежности представляет собой квадратную матрицу, где элемент на пересечении i-й строки и j-го столбца показывает, существует ли ребро между вершинами i и j, а также вес этого ребра. Если ребра нет, ставится значение бесконечность (или очень большое число).

Кратчайший путь из вершины 2 в вершину 5

• Путь 1: 2 -> 1 -> 5 = 10 + 100 = 110
• Путь 2: 2 -> 3 -> 5 = 50 + 10 = 60
• Путь 3: 2 -> 3 -> 4 -> 5 = 50 + 20 + 60 = 130

Кратчайший путь из вершины 2 в вершину 5 равен 60.

Ответ: 60