求图中独立路径的个数

5次浏览(过去30天)

显示旧的注释

哈里 2021年7月15日

0
链接

直接链接到这个问题

//www.tatmou.com/matlabcentral/answers/878933-finding-number-of-independent-pathways-in-a-graph

回答: 克里斯汀Tobler 2021年7月15日

我想要找出图中每个节点对之间独立路径的数量。一个节点对之间的两条路径是独立的，如果它们不共享一个共同的道路链接。为此，我们取一个节点对，找到节点之间的最短路径，删除最短路径上的所有边，然后再次查找该路径，直到找到所有路径。一个节点对之间可能存在的独立路径的最大数目等于节点度的最小值。

我已经为此开发了一个程序，但这似乎工作缓慢。有人能帮我优化一下代码吗?

                         图=图(O_Node D_Node,长度);%从节点和长度生成图
                        
                         度=度(图);%度的节点为矩阵
                        
                         N_Nodes =大小(Graph.Nodes, 1);%图中节点的个数
                        
                         z = 0;
                        
                         m = 0;
                        
                         链接= nchoosek(1:N_Nodes,2);%所有可能的节点对
                        
                         N_Pass = 0(大小(链接,1),1);%每个节点对之间的路径数
                        
                         为i = 1:尺寸(链接,1)%遍历每个节点对
                        
                         z = z + 1;
                        
                         Graph_Temp =图;%创建一个临时图，其边缘将在后续步骤中删除
                        
                         N_Pass (1) = min(学位(链接(我,1),1),学历(链接(我,2),1));可能的最大路径数%等于2个节点的最小次数
                        
                         为k = 1: N_Pass(i,1)
                        
                         通过= shortestpath (Graph_Temp,链接(我,1),链接(我,2));%寻找最短路径
                        
                         如果isempty(通过)
                        
                         打破
                        
                         其他的m = m + 1;计算路径数的%
                        
                         结束
                        
                         Graph_Temp = rmedge (Graph_Temp,通过(1:(大小(通过,2)1)),通过(2:(大小(通过,2))));删除第一条最短路径中包含的所有边
                        
                         通过= [];
                        
                         结束
                        
                         N_Pass_Cal (z, 1) = m;
                        
                         m = 0;
                        
                         结束