4446
правок
Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Материал из WEGA
Поиск кратчайших путей в планарных графах с отрицательными весами ребер (посмотреть исходный код)
Версия от 15:36, 12 мая 2016
, 12 мая 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 32: | Строка 32: | ||
''Уровень декомпозиции'' в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее. | ''Уровень декомпозиции'' в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее. | ||
Для каждого фрагмента декомпозиции рекурсивно вычисляются расстояния по кратчайшим путям между всеми | |||
Для каждого фрагмента декомпозиции рекурсивно вычисляются расстояния по кратчайшим путям между всеми его граничными вершинами, лежащим строго внутри фрагмента. Эти расстояния формируют множество ребер непланарного графа, представляющего кратчайшие пути между граничными вершинами. Плотный граф расстояний планарного графа представляет собой объединение этих графов по всем уровням. | |||
