Exponenta Banner

shortestpathtree

Дерево кратчайшего пути от узла

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

Синтаксис

TR = shortestpathtree(G,s)
TR = shortestpathtree(G,s,t)
TR = shortestpathtree(___,Name,Value)
[TR,D] = shortestpathtree(___)
[TR,D,E] = shortestpathtree(___)

Описание

пример

TR = shortestpathtree(G,s) возвращает ориентированного графа, TR, который содержит дерево кратчайших путей от исходного узла s ко всем другим узлам в графике. Если график взвешивается (то есть, G.Edges содержит переменную Weight), то те веса используются в качестве расстояний вдоль ребер в графике. В противном случае все расстояния ребра взяты, чтобы быть 1.

пример

TR = shortestpathtree(G,s,t) вычисляет дерево кратчайших путей между несколькими исходными или целевыми узлами:

  • s может быть одним исходным узлом, и t может задать несколько целевых узлов.

  • s может задать несколько исходных узлов, и t может задать узел единой цели.

пример

TR = shortestpathtree(___,Name,Value) дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение", с помощью любой из комбинаций входных аргументов в предыдущих синтаксисах. Например, shortestpathtree(G,s,'OutputForm','vector') возвращает числовой вектор, который описывает дерево кратчайшего пути.

пример

[TR,D] = shortestpathtree(___) дополнительно возвращает расстояние кратчайшего пути между узлами в дереве.

[TR,D,E] = shortestpathtree(___) дополнительно возвращает логический векторный E, который указывает, является ли каждое ребро графика в TR.

Примеры

свернуть все

Скрипт Open Live Script

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

Создайте ориентированного графа.

s = [1 1 2 3 3 4 4 6 6 7 8 7 5];
t = [2 3 4 4 5 5 6 1 8 1 3 2 8];
G = digraph(s,t)
G = 
  digraph with properties:

    Edges: [13x1 table]
    Nodes: [8x0 table]

Вычислите кратчайшие пути от узла 1 к каждому из других достижимых узлов в графике. Затем постройте получившееся дерево сверху графика.

TR = shortestpathtree(G,1);
p = plot(G);
highlight(p,TR,'EdgeColor','r')

С тех пор нет никакого пути от узла 1 к узлу 7, узел 7 отключается от дерева.

Скрипт Open Live Script

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

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

s = [1 1 1 1 1 1 1 2 2 7 7 7 7 9 9 3 3 1 6 4 8 10 6 8 4 5];
t = [2 3 4 5 6 8 7 6 7 5 6 8 9 6 8 6 10 10 10 10 10 11 11 11 8 8];
G = graph(s,t);
x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2];
y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0];
plot(G,'XData',x,'YData',y)

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

TR = shortestpathtree(G,'all',10);
plot(TR)

Скрипт Open Live Script

Найдите кратчайшие пути и длины пути от одного исходного узла до нескольких целевых узлов.

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

G = digraph(bucky);
plot(G)

Найдите кратчайшие пути от узла 23 к нескольким другим узлам. Задайте OutputForm как cell, чтобы возвратить кратчайшие пути в массиве ячеек. Задайте два выходных параметров, чтобы также возвратить расстояния кратчайшего пути.

target = [1 5 13 32 44];
[TR,D] = shortestpathtree(G,23,target,'OutputForm','cell')
TR = 5x1 cell array
    {1x6 double}
    {1x5 double}
    {1x8 double}
    {1x6 double}
    {1x6 double}


D = 1×5

     5     4     7     5     5

tree{j} является кратчайшим путем от узла 23 к узлу target(j) с длиной D(j).

Найдите длину пути и длину пути от узла 21 к узлу 5.

path = TR{2}
path = 1×5

    23    22    21     4     5


path_length = D(2)
path_length = 4

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

свернуть все

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

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

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

Исходный узел (узлы), заданный как один или несколько индексов узла или имен узла, или как все узлы в графике с 'all'.

  • Когда используется один, s должен задать один исходный узел.

  • Когда используется вместе с t, s и входные параметры t должны удовлетворить:

    • s может быть одним исходным узлом, и t может задать несколько целевых узлов.

    • s может задать несколько исходных узлов, и t может задать узел единой цели.

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

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

Скаляр

Пример 1

Вектор

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

Имя узла

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

Пример: 'A'

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

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

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

Пример: "A"

StringArray

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

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

Пример: shortestpathtree(G,'a')

Пример: shortestpathtree(G,[1 2 3],8)

Целевой узел (узлы), заданный как один или несколько индексов узла или имен узла, или как все узлы в графике с 'all'.

s и входные параметры t должны удовлетворить:

  • s может быть одним исходным узлом, и t может задать несколько целевых узлов.

  • s может задать несколько исходных узлов, и t может задать узел единой цели.

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

Пример: shortestpathtree(G,[1 2 3],8)

Пример: shortestpathtree(G,{'a','b','c'},{'f'})

Аргументы в виде пар имя-значение

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: [TR,D] = shortestpathtree(G,s,t,'Method','unweighted','OutputForm','vector')

Формат вывода, заданного как пара, разделенная запятой, состоящая из 'OutputForm' и одна из опций в таблице.

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

TR является ориентированным графом, представляющим дерево кратчайшего пути. Если задано, третий вывод E является логическим вектором, указывающим, является ли каждое ребро в TR.

'cell'

TR является массивом ячеек, и TR{k} содержит путь от s до t(k) или от s(k) до t. Если нет никакого пути между узлами, то TR{k} пуст.

Если s и t являются именами узла, то TR{k} является массивом ячеек из символьных векторов. В противном случае TR{k} является числовым вектором.

Если задано, третий вывод E является массивом ячеек, указывающим на ребра на каждом соответствующем пути в TR.

'vector'

TR является вектором, который описывает дерево:

  • Если s содержит один исходный узел, то TR(k) является ID узла, который предшествует узлу k на пути от s до k. Условно, TR(s) = 0.

  • Если s содержит несколько исходных узлов, то TR(k) является ID узла, который следует за узлом k на пути от k до t. Условно, TR(t) = 0.

В каждом случае TR(k) является NaN, если узел k не является частью дерева.

Если задано, третий вывод E является вектором, где E(k) дает индекс ребра дерева кратчайшего пути соединяющийся узел k и узел TR(k).

Пример: shortestpathtree(G,s,'OutputForm','vector')

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

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

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

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

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

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

'unweighted'

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

'positive'

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

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

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

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

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

Алгоритм, разработанный, чтобы улучшать производительность для направленных, графов без петель (DAGs) со взвешенными ребрами.

Используйте isdag, чтобы подтвердить, является ли ориентированный граф нециклическим.

Примечание

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

Пример: shortestpath(G,s,t,'Method','acyclic')

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

свернуть все

Дерево кратчайшего пути, возвращенное как объект digraph, массив ячеек или вектор, в зависимости от значения 'OutputForm'. Используйте функцию highlight, чтобы визуализировать дерево кратчайшего пути сверху графика графика или использовать plot(TR), чтобы визуализировать дерево кратчайшего пути самостоятельно.

Если существует несколько кратчайших путей между двумя узлами, то TR содержит только один из путей. Путь, который возвращен, может измениться, в зависимости от которого алгоритм задан Method. Вывод TR является графиком с нулевыми ребрами, при отсутствии путей, соединяющих ни один из заданных узлов.

Расстояние между входными и выходными узлами, возвращенными как вектор. Значение Inf указывает, что между двумя узлами нет никакого пути.

Ребра в дереве или на пути, возвращенном как логический вектор, массив ячеек или вектор, в зависимости от значения 'OutputForm':

  • Если вы не задаете 'OutputForm' или задаете значение 'tree', то E является логическим вектором, указывающим, является ли каждым ребром графика в ориентированном графе TR. Этот вывод совместим с парой "имя-значение" 'Edges' highlight, например: highlight(p,'Edges',E).

  • Если 'OutputForm' является 'cell', то E является массивом ячеек, содержащим ребра на соответствующих путях в TR.

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

Советы

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

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

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

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

| | | |

Введенный в R2015b

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