graphshortestpath

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

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

Синтаксис

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

Описание

пример

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

пример

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

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

Примеры

свернуть все

Скрипт Open 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'))

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)

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.

Скрипт Open 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'))

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)

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

свернуть все

Матрица смежности в виде 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

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

Пользовательские веса для ребер в матрице 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

Поддержка

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