Exponenta Banner

расстояния

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

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

Синтаксис

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)

Вычислите расстояние кратчайшего пути между всеми парами узла в графике. Поскольку ребра графика не имеют весов, все расстояния ребра взяты, чтобы быть 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)

Найдите расстояния кратчайшего пути от узла 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)

Найдите расстояния кратчайшего пути от узлов 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)

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

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

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

свернуть все

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

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

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

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

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

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

Скаляр

Пример 1

Вектор

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

Имя узла

Символьный вектор

Пример: 'A'

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

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

Скаляр строки

Пример: "A"

StringArray

Пример: ["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 указывает на путь, который не существует.

Советы

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

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

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

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

| | | |

Введенный в R2015b

Документация MATLAB
Поддержка