graphshortestpath

Решите задачу кратчайшего пути в графике

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

Синтаксис

[dist,path,pred] = graphshortestpath(G,S)
[___] = graphshortestpath(G,S,D)
[___] = graphshortestpath(___,Name,Value)

Описание

пример

[dist,path,pred] = graphshortestpath(G,S) определяет кратчайшие пути от исходного узла S ко всем другим узлам в графике G. dist содержит значения расстояния от исходного узла до всех других узлов. path содержит кратчайшие пути к каждому узлу. pred содержит предшествующие узлы кратчайших путей.

пример

[___] = graphshortestpath(G,S,D) определяет кратчайший путь от исходного узла S к целевому узлу D и возвращает любой из выходных аргументов из предыдущего синтаксиса.

[___] = graphshortestpath(___,Name,Value) задает дополнительные опции, используя один или несколько аргументы пары "имя-значение". Задайте аргументы пары "имя-значение" после любой комбинации входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Открыть Live Script

Создайте ориентированный граф с 6 узлами и 11 ребрами.

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
DG = 
   (4,1)       0.4500
   (6,2)       0.4100
   (2,3)       0.5100
   (5,3)       0.3200
   (6,3)       0.2900
   (3,4)       0.1500
   (5,4)       0.3600
   (1,5)       0.2100
   (2,5)       0.3200
   (1,6)       0.9900
   (4,6)       0.3800

Отобразите график.

h = view(biograph(DG,[],'ShowWeights','on'))

Figure Biograph Viewer 1 contains an axes. The axes contains 45 objects of type line, patch, text.

Biograph object with 6 nodes and 11 edges.

Найдите кратчайший путь от узла 1 до узла 6.

[dist,path,pred] = graphshortestpath(DG,1,6)
dist = 0.9500

path = 1×4

     1     5     4     6


pred = 1×6

     0     6     5     5     1     4

Отметьте узлы и ребра кратчайшего пути, раскрасив их красным цветом и увеличив ширину линии.

set(h.Nodes(path),'Color',[1 0.4 0.4])
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
set(edges,'LineColor',[1 0 0])
set(edges,'LineWidth',1.5)

Figure Biograph Viewer 1 contains an axes. The axes contains 45 objects of type line, patch, text.

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

Например, чтобы вычислить самый короткий путь от узла 1 до узла 4 с помощью информации в pred, запрос pred с узлом назначения в качестве первого запроса. Затем используйте возвращенный ответ, чтобы получить следующий узел. Повторите эту процедуру до тех пор, пока ответ на запрос не будет равен 0, что указывает на исходный узел.

next = pred(4)
next = 5

next = pred(next)
next = 1

next = pred(next)
next = 0

Результаты показывают, что самый короткий путь от узла 1 к узлу 4 является 1- > 5- > 4.

Открыть Live Script

Создайте неориентированный граф с 6 узлами и 11 ребрами.

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W);
% tril returns the lower triangular part of the matrix.
UG = tril(DG+DG')
UG = 
   (4,1)       0.4500
   (5,1)       0.2100
   (6,1)       0.9900
   (3,2)       0.5100
   (5,2)       0.3200
   (6,2)       0.4100
   (4,3)       0.1500
   (5,3)       0.3200
   (6,3)       0.2900
   (5,4)       0.3600
   (6,4)       0.3800

Просмотр графика.

h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

Figure Biograph Viewer 1 contains an axes. The axes contains 34 objects of type line, text, patch.

Biograph object with 6 nodes and 11 edges.

Найдите кратчайший путь от узла 1 до узла 6. Задайте 'Directed' на false чтобы указать, что график не является ориентированным графом.

[dist,path,pred] = graphshortestpath(UG,1,6,'Directed',false)
dist = 0.8200

path = 1×4

     1     5     3     6


pred = 1×6

     0     5     5     1     1     3

Отметьте узлы и ребра кратчайшего пути, раскрасив их красным цветом и увеличив ширину линии.

set(h.Nodes(path),'Color',[1 0.4 0.4])
fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID'));
edges = [fowEdges;revEdges];
set(edges,'LineColor',[1 0 0])
set(edges,'LineWidth',1.5)

Figure Biograph Viewer 1 contains an axes. The axes contains 34 objects of type line, text, patch.

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

свернуть все

Матрица смежности, заданная как N -by N разреженная матрица, которая представляет график. Ненулевые значения в матрице представляют веса ребер.

Типы данных: double

Исходный узел, заданный как числовой индекс узла.

Пример: 2

Типы данных: double

Узел назначения, заданный как числовой индекс узла.

Пример: 5

Типы данных: double

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

Задайте необязательные разделенные разделенными запятой парами Name,Value аргументы. Name - имя аргумента и Value - соответствующее значение. Name должны находиться внутри кавычек. Можно задать несколько аргументов в виде пар имен и значений в любом порядке Name1,Value1,...,NameN,ValueN.

Пример: [dist,path,pred] = graphshortestpath(G,1,5,'Method',Acyclic') принимает G быть ориентированным ациклическим графиком при нахождении кратчайшего пути от узла 1 к узлу 5.

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

ОпцияОписание

'Dijkstra' (по умолчанию)

Этот алгоритм принимает, что все веса ребер являются положительными значениями в G. Временная сложность O(log(N)*E), где N и E являются числом узлов и количеством ребер соответственно.

'BFS'

Этот алгоритм поиска первой ширины принимает, что все веса равны и что ребра являются ненулевыми записями в разреженной матрице G. Временная сложность O(N+E).

'Bellman-Ford'

Этот алгоритм принимает, что все веса ребер являются ненулевыми значениями в G. Временная сложность O(N*E).

'Acyclic'

Этот алгоритм принимает, что G является ориентированным ациклическим графиком, и все веса ребер ненулевые значения в G. Временная сложность O(N+E).

Пример: 'Method','Acyclic'

Типы данных: char | string

Ориентированный или неориентированный граф, заданный как разделенная разделенными запятой парами, состоящая из 'Directed' и true или false. Если falseфункция игнорирует верхний треугольник разреженной матрицы G.

Пример: 'Directed',false

Типы данных: logical

Пользовательские веса для ребер в матрице G, заданные как разделенная разделенными запятой парами, состоящая из 'Weights' и вектор-столбец. Вектор должен удовлетворять следующим условиям.

  • Он должен иметь одну запись для каждого ненулевого значения ( ребра) в матрице G.

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

Можно задать нулевые веса. По умолчанию функция получает информацию о весе из ненулевых записей в G.

Пример: 'Weights',[1 2.3 1.3 0 4]

Типы данных: double

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

свернуть все

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

Функция возвращается Inf для недоступных узлов и 0 для исходного узла.

Самые короткие пути от исходного узла ко всем другим узлам, возвращенные как вектор или массив ячеек. Он возвращается как вектор, если вы задаете узел назначения. Каждое число представляет индекс узла в графике.

Предшествующие узлы кратчайших путей, возвращенные как вектор.

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

Функция находит, что самый короткий путь от узла 1 до узла 6 path = [1 5 4 6] и pred = [0 6 5 5 1 4]. Теперь можно определить самые короткие пути от узла 1 до любого другого узла в графике путем индексации в pred. Для примера, чтобы вычислить самый короткий путь от узла 1 до узла 2, можно запросить pred с узлом назначения в качестве первого запроса, затем используйте возвращенный ответ, чтобы получить следующий узел. Повторите эту процедуру до тех пор, пока ответ на запрос не будет равен 0, что указывает на исходный узел.

pred(2) = 6; pred(6) = 4; pred(4) = 5; pred(5) = 1; pred(1) = 0;
Результаты показывают, что самый короткий путь от узла 1 до узла 2 1->5->4->6->2.

Ссылки

[1] Dijkstra, E. W. «A Note on Two Problement in Connexion with Graphs». Numerische Mathematik. Том 1, № 1, 1959, стр. 269-271.

[2] Bellman, R. «О задаче маршрутизации». Ежеквартально по прикладной математике. Том 16, номер 1, стр. 87-90.

[3] Siek, J. G., L. Q. Lee, and A. Lumsdaine. Boost Графика Library: Руководство пользователя и Ссылки Руководство. Upper Saddle River, NJ: Pearson Education, 2002.

См. также

| | | | | | | | | |

Темы

Введенный в R2006b

Документация по Bioinformatics Toolbox

Поддержка

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