Ответы
Ответ дал:
0
Составим матрицу смежности .
Где означает отстутствие пути (ребра) между вершинами.
Составим по ней матрицу кратчайших путей .
Пусть , а
- длина пути из
в
.
Пусть - множество вершин.
Рассмотрим вершины . Если кратчайший путь между
и
проходит через вершину
, то
, иначе,
. Тогда
.
Составим алгоритм на псевдокоде:
.
Вообще, сложность алгоритма и при
, количество операций
. Делать 125 сравнений - несколько много. Приведу лишь итоговую матрицу:
Вас заинтересует
2 года назад
2 года назад
7 лет назад
8 лет назад
8 лет назад