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 являются числом узлов и кромками соответственно.

[...] = графические пути (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] Johnson, D.B. (1977). Эффективные алгоритмы для кратчайших путей в разреженных сетях. Журнал ACM 24 (1), 1-13.

[2] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).

См. также

Введенный в R2006b

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