Exponenta Banner

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) задает дополнительные опции с помощью одного или нескольких аргументов пары "имя-значение". Задайте аргументы пары "имя-значение" после любой из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Открыть скрипт

Создайте ориентированного графа с 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'))

Biograph object with 6 nodes and 11 edges.

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

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

dist =

    0.9500


path =

     1     5     4     6


pred =

     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)

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

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

next = pred(4)
next = pred(next)
next = pred(next)

next =

     5


next =

     1


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'))

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     5     3     6


pred =

     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)

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

свернуть все

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

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

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

Пример 2

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

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

Пример 5

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

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

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

ОпцияDesciption

'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

Типы данных: логический

Пользовательские веса для ребер в матрице 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] Дейкстра, E. W. "Примечание по Двум проблемам в Связи с Графиками". Numerische Mathematik. Издание 1, Номер 1, 1959, стр 269–271.

[2] Белман, R. "На проблеме Маршрутизации". Ежеквартально Прикладной математики. Издание 16, Номер 1, стр 87–90.

[3] Siek, J. G. Л. К. Ли и А. Ламсдэйн. Библиотека графика повышения: руководство пользователя и справочник. Верхний Сэддл-Ривер, NJ: образование Пирсона, 2002.

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

| | | | | | | | | |

Темы

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

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