Exponenta Banner
exponenta event banner

graphshortestpath

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

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

Синтаксис

[dist, path, pred] = graphshortestpath (G , S)
[___] = graphshortestpath (G, S, D)
[___] = graphshortestpath (___, имя, значение)

Описание

пример

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

пример

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

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

Примеры

свернуть все

Открыть сценарий в реальном времени

Создайте направленный граф с 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.

Открыть сценарий в реальном времени

Создайте неориентированный график с 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-на-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] Дийкстра, Е. В. «Примечание о двух проблемах в соединении с графиками». Numerische Mathematik. Том 1, номер 1, 1959, стр. 269-271.

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

[3] Сиек, Дж. Г., Л. К. Ли и А. Лумсдейн. Библиотека Boost Graph: Руководство пользователя и справочное руководство. Upper Saddle River, Нью-Джерси: Pearson Education, 2002.

См. также

| | | | | | | | | |

Темы

Представлен в R2006b

Документация по инструментарию биоинформатики

Поддержка