1313
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 03:18, 20 ноября 2024
, 20 ноября 2024→Применение
Irina (обсуждение | вклад) мНет описания правки |
KVN (обсуждение | вклад) |
||
| Строка 69: | Строка 69: | ||
== Применение == | == Применение == | ||
Эксцентриситетом вершины v называется наибольшее расстояние от v до любой другой вершины графа. Диаметр графа равен наибольшему эксцентриситету для любой вершины. Иными словами, диаметр представляет собой наибольшее расстояние между любой парой вершин. Если задача нахождения кратчайших путей между всеми парами вершин решена, максимальный элемент матрицы будет равен ее диаметру. | [[Эксцентриситет вершины|Эксцентриситетом вершины]] v называется наибольшее расстояние от v до любой другой вершины графа. [[Диаметр|Диаметр графа]] равен наибольшему эксцентриситету для любой вершины. Иными словами, диаметр представляет собой наибольшее расстояние между любой парой вершин. Если задача нахождения кратчайших путей между всеми парами вершин решена, максимальный элемент матрицы будет равен ее диаметру. | ||
== Открытые вопросы == | == Открытые вопросы == | ||