distances

Расстояния кратчайшего пути всех пар узла

свернуть все на странице

Синтаксис

d = distances(G)
d = distances(G,s)
d = distances(G,s,t)
d = distances(___,'Method',algorithm)

Описание

пример

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.

Примеры

свернуть все

Скрипт Open Live Script

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

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 object. The axes object 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
Скрипт Open Live Script

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

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 object. The axes object 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
Скрипт Open Live Script

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

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 object. The axes object 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
Скрипт Open Live Script

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

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 object. The axes object 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. 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' (значение по умолчанию)

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

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

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

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

'unweighted'

Расчет в ширину, который обрабатывает весь вес ребра как 1.

'positive'

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

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

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

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

Примечание

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

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

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

свернуть все

Расстояния кратчайшего пути между парами узла, возвращенными как матрица. Размер d (# исходные узлы) целевыми узлами (#). Значение Inf указывает на путь, который не существует.

Советы

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

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

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

Смотрите также

| | | |

Введенный в R2015b

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

Поддержка

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