кратчайший путь

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

Синтаксис

P = shortestpath(G,s,t)
P = shortestpath(G,s,t,'Method',algorithm)
[P,d] = shortestpath(___)
[P,d,edgepath] = 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)

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

свернуть все

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

Пример: 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 пуст, {}, если нет никакого пути между узлами.

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

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

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

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

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

Советы

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

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

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

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

| | | |

Введенный в R2015b

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