ЕГЭОГЭ
Задания № 13, 27 · ЕГЭ

Таблица кратчайших расстояний

Как записывают минимальные расстояния между вершинами графа
2 мин чтенияСложность: Обновлено 29 сентября 2026

Таблица кратчайших расстояний — это таблица, в которой для каждой пары вершин графа записано минимальное возможное расстояние между ними. Она помогает быстро находить длину кратчайшего пути и используется в задачах на матрицы, маршруты и анализ графов.

Таблица кратчайших расстоянийОбозначение $d_{ij}$ читают как «расстояние от вершины $i$ до вершины $j$».
Квадратная таблица \(D=(d_{ij})\), где \(d_{ij}\) — длина кратчайшего пути из вершины \(i\) в вершину \(j\). Если путь из \(i\) в \(j\) отсутствует, в таблице обычно записывают специальный символ, например \(\infty\) или большое число. Расстояние от вершины до самой себя равно нулю: \(d_{ii}=0\).

Как устроена таблица

Строка соответствует начальной вершине, столбец — конечной. В неориентированном графе расстояния симметричны: \(d_{ij}=d_{ji}\). В ориентированном графе это необязательно: путь из \(i\) в \(j\) может существовать, а обратного пути может не быть. Расстояние считают по сумме весов рёбер, а не по количеству промежуточных вершин.

\[d_{ij}=\min\{\text{сумма весов рёбер всех путей из }i\text{ в }j\}\]
№
Короткий пример

Пусть есть рёбра \(A-B\) с весом \(4\), \(A-C\) с весом \(2\) и \(C-B\) с весом \(1\). Для пары \(A,B\) прямой путь имеет длину \(4\), а путь \(A-C-B\) — \(2+1=3\). Поэтому в таблице на пересечении строки \(A\) и столбца \(B\) записывают \(d_{AB}=3\).

!
Не путайте

Таблица кратчайших расстояний не является исходной таблицей смежности. В таблице смежности обычно указано, есть ли ребро между вершинами и каков его вес, а в таблице расстояний учитываются все возможные маршруты. Таблицу расстояний можно получить, например, с помощью алгоритма Флойда; для одной начальной вершины часто применяют алгоритм Дейкстры.

Использование в экзаменационных задачах

В задачах ЕГЭ сначала определяют, что означает строка и столбец, затем находят нужную пару вершин и сравнивают длины возможных маршрутов. Если требуется маршрут между несколькими пунктами, выбирают последовательность переходов с минимальной суммой весов. Важно проверить направление рёбер и единицы измерения расстояний.

Проверьте себя

В графе есть пути \(A-B\) длины \(7\) и \(A-C-B\) длины \(3+2\). Какое значение должно стоять в таблице на месте \(d_{AB}\)?

Главное за минуту

Главное

  • \(d_{ij}\) — минимальная длина пути из вершины \(i\) в вершину \(j\).
  • На диагонали таблицы стоят нули; в неориентированном графе таблица симметрична.
  • При решении задач сравнивают суммы весов всех подходящих маршрутов, учитывая направление рёбер.