Метрика кратчайшего пути
в теории графов - число рёбер в кратчайшем пути / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Расстояние (теория графов)?
Кратко изложите эту статью для 10-летнего ребёнка
ПОКАЗАТЬ ВСЕ ВОПРОСЫ
Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между данными вершинами. Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным.
В случае ориентированных графов расстояние между двумя вершинами
и
определяется как длина кратчайшего пути из
в
, состоящий из дуг[1]. В отличие от случая неориентированных графов
может не совпадать с
и даже может случиться, что одно расстояние существует, а другое — нет.