主要内容

graphshortestPath.

解决图中的最短路径问题

折叠所有页面

语法

[dist，path，pred] = graphshortestpath（g，s）
［＿＿＿] = graphshortestPath（g，s，d）
［＿＿＿] = graphshortestPath（＿＿＿，名称，价值）

描述

例子

［dist，路径，pred] = graphshortestPath（G，年代）确定到源节点的最短路径年代到图表中的所有其他节点G．dist包含从源节点到所有其他节点的距离。路径包含每个节点的最短路径。pred包含最短路径的前任节点。

例子

［＿＿＿] = graphshortestPath（G，年代，D）确定来自源节点的最短路径年代到目标节点D并返回以前语法中的任何输出参数。

［＿＿＿] = graphshortestPath（＿＿＿，名称，价值）使用一个或多个名称-值对参数指定其他选项。在前面语法中的任何输入参数组合之后指定名称-值对参数。

例子

全部收缩

打开直播脚本

创建一个带有6个节点和11个边的定向图。

w = [.41 .99 .51 .32 .15。45 .21];dg =稀疏（[61 2 2 3 4 4 5 5 6 1]，[2 6 3 5 4 11 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 0.3800(4、6)

显示图形。

h =视图(生物运动描记器(DG, [],'展示重量'，“上”）））

图传记查看器1包含一个轴。轴包含45个类型为line, patch, text的对象。

具有6个节点和11个边缘的传记对象。

求节点1到节点6的最短路径。

[dist，path，pred] = graphshortestpath（dg，1,6）
dist = 0.9500
路径=1×41 5 4 6
pred =1×60 6 5 5 1 4

用红色标记最短路径的节点和边并增加线宽。

设置（h.nodes（路径），'颜色'，[1 0.4 0.4]）边缘= getEdgesByNodeID（h，get（h.nodes（路径），'ID'));集(边缘,'linecolor'，[1 0 0]）设置（边缘，'行宽'，1.5）

图传记查看器1包含一个轴。轴包含45个类型为line, patch, text的对象。

pred包含从节点1，源节点到所有其他节点的最短路径的前任节点，不仅是指定的目标节点。您可以使用pred查询从源节点到图中任何其他节点的最短路径。

例如，使用信息中的信息弄错节点1到节点4的最短路径pred， 询问pred使用目标节点作为第一个查询。然后使用返回的答案获取下一个节点。重复此过程，直到您将查询答案答案为0，表示源节点。

下一个= pred（4）
下一个= 5
下一个= pred（下一个）
下一个= 1
下一个= pred（下一个）
下一个= 0

结果表明节点1到节点4的最短路径为1-> 5-> 4。

打开直播脚本

创建一个具有6个节点和11条边的无向图。

w = [.41 .99 .51 .32 .15。45 .21];DG = sparse([6 1 2 2 3 4 4 5 5 6 1]，[2 6 3 5 4 4 5]，W);返回矩阵的下三角部分。UG =下三角阵(DG + ')
UG =(4,1) 0.4500(5、1)0.2100 (6,1)0.9900 (2)0.5100 (2)0.3200 (6 2)0.4100 (4,3)0.1500 (5,3)0.3200 (6 3)0.2900 (5,4)0.3600 0.3800 (6,4)

查看图。

h =视图(生物运动描记器(UG, [],'展览'，'离开'，'展示重量'，“上”）））

图传记查看器1包含一个轴。轴包含34个类型为line, text, patch的对象。

具有6个节点和11个边缘的传记对象。

求节点1到节点6的最短路径。集'指示'来错误的指定该图不是有向图。

[dist，path，pred] = graphshortestpath（ug，1,6，'指示'，错误的）
dist = 0.8200
路径=1×41 5 3 6
pred =1×63 .你的老板很好

用红色标记最短路径的节点和边并增加线宽。

设置（h.nodes（路径），'颜色'，[1 0.4 0.4]）fowedges = getEdgesByNodeID（h，get（h.nodes（路径），'ID'));revEdges = getedgesbynodeid (h,得到(h.Nodes (fliplr(路径)),'ID'));边缘= [fowEdges; revEdges];集(边缘,'linecolor'，[1 0 0]）设置（边缘，'行宽'，1.5）

图传记查看器1包含一个轴。轴包含34个类型为line, text, patch的对象。

输入参数

全部收缩

邻接矩阵，指定为一个N-经过-N表示图形的稀疏矩阵。矩阵中的非零条目表示边缘的权重。

数据类型：双倍的

源节点，指定为数字节点索引。

例子：2

数据类型：双倍的

目标节点，指定为数字节点索引。

例子：5

数据类型：双倍的

名称值对参数

指定可选的逗号分隔的对名称，价值论点。的名字参数名和价值是相应的价值。的名字必须出现在引号内。您可以以任何顺序指定多个名称和值对参数name1，value1，...，namen，valuen．

例子：(距离、路径,pred) = graphshortestpath (G, 1, 5‘方法’,非循环”)假设G当从节点找到最短路径时，是一个有向无环图1节点5．

最短路径算法，指定为逗号分隔对组成“方法”其中一个选项。

选项 描述

'dijkstra'（默认）

该算法假设所有边的权值都是正的G．时间复杂性是o（日志（N）*E）， 在哪里N和E分别为节点数和边数。

“石”

这种广度第一搜索算法假定所有权重都相等，并且边缘是稀疏矩阵中的非零条目G．时间复杂性是o（N+E）．

'Bellman-Ford'

该算法假设所有边的权值都是非零项G．时间复杂性是o（N＊E）．
'acyclic'

这个算法假设G是一个定向的无循环图形，所有边缘权重都是非零条目G．时间复杂性是o（n + e）．

例子：'方法'，'acyclic'

数据类型：char|字符串

指定或无向图形标志，指定为逗号分隔对组成'指示'和真的要么错误的．如果错误的时，函数忽略稀疏矩阵的上三角G．

例子：'指示'，假

数据类型：逻辑

矩阵G中边的自定义权值，指定为逗号分隔的对，由“重量”和一栏矢量。载体必须符合以下条件。

  • 它必须在矩阵中的每个非零值（边缘）有一个条目G．

  • 向量中自定义权值的顺序必须与中的非零值的顺序匹配G当它按列遍历时。

您可以指定零值的权重。默认情况下，该函数从非零条目中获取权重信息G．

例子：'重量'，[1 2.3 1.3 0 4]

数据类型：双倍的

输出参数

全部收缩

源节点到图中所有其他节点的距离，以数字标量或向量的形式返回。dist如果指定目标节点作为第三个输入参数，则作为标量返回。

函数返回INF.对于不可达的节点和0用于源节点。

从源节点到所有其他节点的最短路径，作为向量或单元数组返回。如果指定目标节点，则将其作为向量返回。每个数字表示图中的节点索引。

最短路径的前任节点，作为向量返回。

您可以使用pred确定从源节点到所有其他节点的最短路径。假设你有一个有6个节点的有向图。

该功能发现从节点1到节点6的最短路径是路径= [1 5 4 6]和pred = [0 6 5 5 1 4]．现在您可以通过索引into来确定从节点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.“关于与图形连接中的两个问题的说明。”Numerische Mathematik。卷。1，第1,1959，第269.271页。

[2] Bellman，R。“在路由问题上。”应用数学季度。卷。16，数字1，pp。87-90。

[3] Siek，J.G.，L. Q. Lee和A. Lumsdaine。Boost Graph库：用户指南和参考手册。上部马鞍河，新泽西：皮尔逊教育，2002年。

另请参阅

||||||||||

话题

介绍了R2006b

生物信息学工具箱文档

金宝app

尝试MATLAB, Si金宝appmulink和其他产品下载188bet金宝搏

立即获得审判