shortestpath

Кратчайший путь между двумя одним узлами

Описание

пример

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

пример

P = shortestpath(G,s,t,'Method',algorithm) опционально задает алгоритм, чтобы использовать в вычислении кратчайшего пути. Например, если G взвешенный график, затем shortestpath(G,s,t,'Method','unweighted') игнорирует вес ребра в G и вместо этого обработки весь вес ребра как 1.

пример

[P,d] = shortestpath(___) дополнительно возвращает длину кратчайшего пути, d, использование любого из входных параметров в предыдущих синтаксисах.

пример

[P,d,edgepath] = shortestpath(___) дополнительно возвращает индексы ребра edgepath из всех ребер на кратчайшем пути от s к t.

Примеры

свернуть все

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

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);
plot(G)

Вычислите кратчайший путь между узлами 7 и 8.

P = shortestpath(G,7,8)
P = 1×5

     7     1     3     5     8

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

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

Найдите кратчайший путь между узлами 3 и 8 и задайте два выходных параметров, чтобы также возвратить длину пути.

[P,d] = shortestpath(G,3,8)
P = 1×5

     3     9     5     7     8

d = 4

Поскольку ребра в центре графика имеют большие веса, кратчайший путь между узлами 3 и 8 обходит контур графика, где вес ребра является наименьшим. Этот путь имеет общую длину 4.

Создайте и постройте график со взвешенными ребрами, с помощью пользовательских координат узла.

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

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];
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

Найдите кратчайший путь между узлами 6 и 8 на основе веса ребра графика. Подсветите этот путь зеленого цвета.

[path1,d] = shortestpath(G,6,8)
path1 = 1×5

     6     3     1     4     8

d = 14
highlight(p,path1,'EdgeColor','g')

Задайте Method как unweighted проигнорировать вес ребра, вместо этого обрабатывая все ребра, как будто у них был вес 1. Этот метод производит различный путь между узлами, тот, который ранее имел слишком большой из длины пути, чтобы быть кратчайшим путем. Подсветите этот путь красного цвета.

[path2,d] = shortestpath(G,6,8,'Method','unweighted')
path2 = 1×3

     6     9     8

d = 2
highlight(p,path2,'EdgeColor','r')

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

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

G = graph([1 1 1 1 1 2 2 3 3 3 4 4],[2 2 2 2 2 3 4 4 5 5 5 2],[2 4 6 8 10 5 3 1 5 6 8 9]);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Найдите кратчайший путь между узлом 1 и узлом 5. Поскольку несколько из пар узла имеют больше чем одно ребро между ними, задают три выходных параметров к shortestpath возвратить определенные ребра, которые пересекает кратчайший путь.

[P,d,edgepath] = shortestpath(G,1,5)
P = 1×5

     1     2     4     3     5

d = 11
edgepath = 1×4

     1     7     9    10

Результаты показывают, что кратчайший путь имеет общую длину 11 и следует за ребрами, данными G.Edges(edgepath,:).

G.Edges(edgepath,:)
ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       2   
     2    4       3   
     3    4       1   
     3    5       5   

Подсветите этот путь к ребру при помощи highlight функция с 'Edges' пара "имя-значение", чтобы задать индексы пересеченных ребер.

highlight(p,'Edges',edgepath)

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

свернуть все

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

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

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

Входные и выходные идентификаторы узла в виде отдельных аргументов индексов узла или имен узла.

ЗначениеПример
Скалярный индекс узла1
Имя узла вектора символов'A'
Имя узла строкового скаляра"A"

Пример: shortestpath(G,2,5) вычисляет кратчайший путь между узлом 2 и узлом 5.

Пример: shortestpath(G,'node1','node2') вычисляет кратчайший путь между именованными узлами node1 и node2.

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

ОпцияОписание
'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')

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

свернуть все

Кратчайший путь между узлами, возвращенными как вектор индексов узла или массив имен узла. P isempty, если нет никакого пути между узлами.

  • Если s и t содержите числовые индексы узла, затем P числовой вектор индексов узла.

  • Если s и t содержите имена узла, затем P массив ячеек или массив строк, содержащий имена узла.

Если существует несколько кратчайших путей между s и t, затем P содержит только один из путей. Путь, который возвращен, может измениться в зависимости от который алгоритм Method задает.

Расстояние кратчайшего пути, возвращенное в виде числа. d суммирование веса ребра между последовательными узлами в P. Если нет никакого пути между узлами, то d isinf.

Ребра на кратчайшем пути, возвращенном как вектор индексов ребра. Для мультиграфов этот выход указывает, какое ребро между двумя узлами находится на пути. Этот выход совместим с 'Edges' пара "имя-значение" highlight, например: highlight(p,'Edges',edgepath).

Советы

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

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

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

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

| | | |

Введенный в R2015b

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