distances

Самые короткие расстояния пути для всех пар узлов

Описание

пример

d = distances(G) возвращает матрицу, d, где d(i,j) - длина кратчайшего пути между узлами i и узловые j. Если график взвешен (то есть G.Edges содержит переменную Weight), затем эти веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния по ребрам будут 1.

пример

d = distances(G,s) ограничивает исходные узлы узлами, определенными s, таким образом d(i,j) расстояние от узла s(i) к узлу j.

пример

d = distances(G,s,t) дополнительно ограничивает целевые узлы узлами, определяемыми t, таким образом d(i,j) расстояние от узла s(i) к узлу t(j).

пример

d = distances(___,'Method',algorithm) опционально задает алгоритм, который будет использоваться при вычислении кратчайшего пути с использованием любого из входных параметров в предыдущих синтаксисах. Для примера, если G является взвешенным графиком, тогда distances(G,'Method','unweighted') игнорирует веса кромок в G и вместо этого рассматривает все веса кромок как 1.

Примеры

свернуть все

Создайте и постройте график.

s = [1 1 1 2 5 5 5 8 9];
t = [2 3 4 5 6 7 8 9 10];
G = graph(s,t);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Вычислите самое короткое расстояние пути между всеми парами узлов в графике. Поскольку ребра графика не имеют весов, все расстояния ребра приняты равными 1.

d = distances(G)
d = 10×10

     0     1     1     1     2     3     3     3     4     5
     1     0     2     2     1     2     2     2     3     4
     1     2     0     2     3     4     4     4     5     6
     1     2     2     0     3     4     4     4     5     6
     2     1     3     3     0     1     1     1     2     3
     3     2     4     4     1     0     2     2     3     4
     3     2     4     4     1     2     0     2     3     4
     3     2     4     4     1     2     2     0     1     2
     4     3     5     5     2     3     3     1     0     1
     5     4     6     6     3     4     4     2     1     0

d симметрично, потому что G является неориентированным графом. В общем d(i,j) - длина кратчайшего пути между узлами i и узловые j, и для неориентированных графов это эквивалентно d(j,i).

Для примера найдите длину кратчайшего пути между узлом 1 и узлом 10.

d(1,10)
ans = 5

Создайте и постройте график.

s = [1 1 1 1 2 2 3 4 4 5 6];
t = [2 3 4 5 3 6 6 5 7 7 7];
G = graph(s,t);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Найдите самые короткие расстояния пути от узла 1, узла 2 и узла 3 до всех других узлов в графике.

d = distances(G,[1 2 3])
d = 3×7

     0     1     1     1     1     2     2
     1     0     1     2     2     1     2
     1     1     0     2     2     1     2

Использование d чтобы найти кратчайший путь расстояние от узла 1 до узла 7.

d(1,7)
ans = 2

Создайте и постройте график.

s = [1 1 1 2 2 3 3 4 5 5 6 7 8  8 10 11];
t = [2 3 10 4 12 5 4 6 6 7 9 8 9 11 11 12];
G = graph(s,t);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Найдите самые короткие расстояния пути от узлов 5 и 7 до узлов 2 и 3.

sources = [5 7];
targets = [2 3];
d = distances(G,sources,targets)
d = 2×2

     3     1
     4     2

Использование d чтобы найти кратчайший путь расстояние между узлом 7 и узлом 3. В этом случае d(i,j) расстояние от узла sources(i) к узлу targets(j).

d(2,2)
ans = 2

Создайте и постройте график ориентированного графа с взвешенными кромками.

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Figure contains an axes. The axes contains an object of type graphplot.

Найдите кратчайшее расстояние пути между всеми парами узлов графика.

d = distances(G)
d = 8×8

     0    90    10    10   100    30    40   Inf
   Inf     0    20    50    10    40    80   Inf
   Inf   110     0    30   120    20    60   Inf
   Inf    80   100     0    90   120    30   Inf
   Inf   120    10    40     0    30    70   Inf
   Inf    90   110    10   100     0    40   Inf
   Inf    50    70   100    60    90     0   Inf
   Inf   100    20    20    10    10    50     0

Начиная с G является ориентированным графом, d не симметрично, и d(i,j) соответствует расстоянию между узлами i и j. The Inf значения в d соответствуют узлам, которые недоступны. Для примера, поскольку узел 1 не имеет предшественников, невозможно достичь узла 1 от любого другого узла в графике. Итак, первый столбец d содержит много Inf значения, отражающие, что узел 1 недоступен.

По умолчанию distances использует веса кромок для вычисления расстояний. Задайте 'Method' как 'unweighted' чтобы игнорировать веса кромок и считать все расстояния ребер равными 1.

d1 = distances(G,'Method','unweighted')
d1 = 8×8

     0     1     1     1     2     2     2   Inf
   Inf     0     2     4     1     3     5   Inf
   Inf     4     0     2     5     1     3   Inf
   Inf     2     4     0     3     5     1   Inf
   Inf     5     1     3     0     2     4   Inf
   Inf     3     5     1     4     0     2   Inf
   Inf     1     3     5     2     4     0   Inf
   Inf     2     2     2     1     1     1     0

Входные параметры

свернуть все

Входной график, заданный как graph или digraph объект. Использование graph для создания неориентированного графа или digraph для создания ориентированного графа.

Пример: G = graph(1,2)

Пример: G = digraph([1 2],[2 3])

Исходные узлы, заданные как один или несколько индексов узлов или имен узлов или 'all' для выбора всех исходных узлов.

В этой таблице показаны различные способы обращения к одному или нескольким узлам либо по их числовым индексам узлов, либо по их именам узлов.

ФормаОдин узелНесколько узлов
Индекс узла

Скаляр

Пример: 1

Вектор

Пример: [1 2 3]

Имя узла

Вектор символов

Пример: 'A'

Массив ячеек из символьных векторов

Пример: {'A' 'B' 'C'}

Строковый скаляр

Пример: "A"

Строковые массивы

Пример: ["A" "B" "C"]

s и t не должны указывать узлы с именем 'all' или 'Method', поскольку эти имена узлов конфликтуют с именами опций. Использование findnode вместо этого передайте индекс узла для этих случаев.

Пример: distances(G,[1 2])

Пример: distances(G,'all',[1 3 5])

Целевые узлы, заданные как один или несколько индексов узлов или имен узлов или 'all' для выбора всех целевых узлов.

s и t не должны указывать узлы с именем 'all' или 'Method', поскольку эти имена узлов конфликтуют с именами опций. Использование findnode вместо этого передайте индекс узла для этих случаев.

Пример: distances(G,[1 2])

Пример: distances(G,'all',[1 3 5])

Алгоритм кратчайшего пути, заданный как один из опций в таблице.

ОпцияОписание
'auto' (по умолчанию)

The 'auto' опция автоматически выбирает алгоритм:

  • 'unweighted' используется для graph и digraph входы без весов кромок.

  • 'positive' используется для всех graph входы, которые имеют веса кромок и требуют, чтобы веса были неотрицательными. Эта опция также используется для digraph входы с неотрицательными весами кромок.

  • 'mixed' используется для digraph входы, веса которых содержат некоторые отрицательные значения. График не может иметь отрицательных циклов.

'unweighted'

Breadth - первый расчет, которое рассматривает все веса ребер как 1.

'positive'

Алгоритм Дейкстры, который требует, чтобы все веса ребер были неотрицательными.

'mixed' (только для digraph)

Алгоритм Беллмана-Форда для ориентированных графов, который требует, чтобы график не имел отрицательных циклов.

Пока 'mixed' медленнее 'positive' для той же задачи, 'mixed' является более универсальным, так как позволяет некоторым весам ребер быть отрицательными.

Примечание

Для большинства графиков 'unweighted' является самым быстрым алгоритмом, далее следуют 'positive', и 'mixed'.

Пример: distances(G,s,t,'Method','unweighted')

Выходные аргументы

свернуть все

Самые короткие пути расстояния между парами узлов, возвращенные как матрица. Размер d is (# source nodes) -by- (# target nodes). Значение Inf указывает путь, который не существует.

Совет

  • The shortestpath, shortestpathtree, и distances функции не поддерживают неориентированные графы с отрицательными весами ребер или вообще любой график, содержащий отрицательный цикл, по этим причинам:

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

    • Один отрицательный вес ребра в неориентированном графе создает отрицательный цикл.

Введенный в R2015b
Для просмотра документации необходимо авторизоваться на сайте