graphallshortestpaths

Поиск всех кратчайших путей в графике

Синтаксис

[dist] = graphallshortestpaths(G) [dist] = graphallshortestpaths(G, ...'Directed', DirectedValue, ...) [dist] = graphallshortestpaths(G, ...'Weights', WeightsValue, ...)

Аргументы

`G`	N-на-N разреженная матрица, представляющая граф. Ненулевые записи в матрице `G` представляют веса кромок.
`DirectedValue`	Свойство, указывающее, направлен или не направлен график. Войти `false` для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: `true`.
`WeightsValue`	Вектор столбца, задающий пользовательские веса для ребер в матрице `G`. Он должен иметь одну запись для каждого ненулевого значения (края) в матрице `G`. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в матрице `G` при пересечении по столбцам. Это свойство позволяет использовать веса с нулевым значением. По умолчанию `graphallshortestpaths` получает информацию о весе из ненулевых записей в матрице `G`.

Описание

Совет

Вводные сведения о функциях теории графов см. в разделе Функции теории графов.

[dist] = graphallshortestpaths(G) поиск кратчайших путей между каждой парой узлов в графе, представленных матрицей G, используя алгоритм Джонсона. Вход G - разреженная матрица N-на-N, представляющая граф. Ненулевые записи в матрице G представляют веса кромок.

Продукция dist - матрица N-на-N, где dist(S,T) - расстояние кратчайшего пути от исходного узла S в целевой узел T. Элементы в диагонали этой матрицы всегда 0, указывая, что исходный узел и целевой узел одинаковы. A 0 нет в диагонали указывает, что расстояние между исходным узлом и целевым узлом 0. Один Inf указывает на отсутствие пути между исходным узлом и целевым узлом.

Алгоритм Джонсона имеет временную сложность O(N*log(N)+N*E), где N и E - количество узлов и рёбер соответственно.

[...] = graphallshortestpaths (G, 'PropertyName', PropertyValue, ...) требования graphallshortestpaths с необязательными свойствами, использующими пары имя/значение свойства. Можно указать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и не чувствителен к регистру. Эти пары имя/значение свойства следующие:

[dist] = graphallshortestpaths(G, ...'Directed', DirectedValue, ...) указывает, направлен или не направлен график. Набор DirectedValue кому false для неориентированного графа. Это приводит к игнорированию верхнего треугольника разреженной матрицы. По умолчанию: true.

[dist] = graphallshortestpaths(G, ...'Weights', WeightsValue, ...) позволяет задать пользовательские веса для ребер. WeightsValue является вектором-столбцом, имеющим одну запись для каждого ненулевого значения (ребра) в матрице G. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в матрице G при пересечении по столбцам. Это свойство позволяет использовать веса с нулевым значением. По умолчанию graphallshortestpaths получает информацию о весе из ненулевых записей в матрице G.

Примеры

Пример 31. Поиск всех кратчайших путей в направленном графике

Создайте и просмотрите направленный график с 6 узлами и 11 ребрами.

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)

DG =

   (4,1)       0.4500
   (6,2)       0.4100
   (2,3)       0.5100
   (5,3)       0.3200
   (6,3)       0.2900
   (3,4)       0.1500
   (5,4)       0.3600
   (1,5)       0.2100
   (2,5)       0.3200
   (1,6)       0.9900
   (4,6)       0.3800

view(biograph(DG,[],'ShowWeights','on'))

Найдите все самые короткие пути между каждой парой узлов в направленном графе.
```
graphallshortestpaths(DG)

ans =

         0    1.3600    0.5300    0.5700    0.2100    0.9500
    1.1100         0    0.5100    0.6600    0.3200    1.0400
    0.6000    0.9400         0    0.1500    0.8100    0.5300
    0.4500    0.7900    0.6700         0    0.6600    0.3800
    0.8100    1.1500    0.3200    0.3600         0    0.7400
    0.8900    0.4100    0.2900    0.4400    0.7300         0
```
Результирующая матрица показывает кратчайший путь от узла 1 (первая строка) к узлу 6 (шестой столбец) равен 0,95. Это можно увидеть на графике, отслеживая путь от узла 1 к узлу 5 к узлу 4 к узлу 6 (0,21 + 0,36 + 0,38 = 0,95).

Пример 32. Поиск всех кратчайших путей в неориентированном графике

Создайте и просмотрите неориентированный график с 6 узлами и 11 ребрами.

UG = tril(DG + DG')

UG =

   (4,1)       0.4500
   (5,1)       0.2100
   (6,1)       0.9900
   (3,2)       0.5100
   (5,2)       0.3200
   (6,2)       0.4100
   (4,3)       0.1500
   (5,3)       0.3200
   (6,3)       0.2900
   (5,4)       0.3600
   (6,4)       0.3800

view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

Найдите все самые короткие пути между каждой парой узлов в неориентированном графе.
```
graphallshortestpaths(UG,'directed',false)

ans =

         0    0.5300    0.5300    0.4500    0.2100    0.8300
    0.5300         0    0.5100    0.6600    0.3200    0.7000
    0.5300    0.5100         0    0.1500    0.3200    0.5300
    0.4500    0.6600    0.1500         0    0.3600    0.3800
    0.2100    0.3200    0.3200    0.3600         0    0.7400
    0.8300    0.7000    0.5300    0.3800    0.7400         0
```
Результирующая матрица симметрична, так как представляет неориентированный граф. Он показывает кратчайший путь от узла 1 (первая строка) к узлу 6 (шестой столбец) равен 0,83. Это можно увидеть на графике, отслеживая путь от узла 1 к узлу 4 к узлу 6 (0,45 + 0. 38 = 0.83). Поскольку UG является неориентированным графом, мы можем использовать ребро между узлом 1 и узлом 4, что мы не могли сделать в направленном графе DG.

Ссылки

[1] Джонсон, Ди Би (1977). Эффективные алгоритмы для кратчайших путей в разреженных сетях. Журнал ACM 24 (1), 1-13.

[2] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

Представлен в R2006b

Документация