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=5×1 cell
    {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

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

свернуть все

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

Пример: 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"

Массив строк

Пример: ["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 имя аргумента и 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} isempty.

Если 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) isnan если узел 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' iscell, затем E массив ячеек, содержащий ребра на соответствующих путях в TR.

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

Советы

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

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

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

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

| | | |

Введенный в R2015b

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