Finding number of independent pathways in a graph

I want to find the number of independent pathways between each node pair in a graph. 2 pathways between a node pair is said to be independent if they do not share a common road link. For this we take a node pair, find the shortest path between the nodes, remove all the edges in the shortest path, and find the path again till all paths are found. The maximum number of independent pathways possible between a node pair is equal to the minimum of the degree of the nodes.

I have developed a program for this but this seems to be working slow. Can somebody help me optimse the code.

Graph= graph(O_Node,D_Node,Length); %making graph from nodes and length
Degree=degree(Graph);%degree of nodes as matrix
N_Nodes=size(Graph.Nodes,1);% No of nodes in the graph
z=0;
m=0;
Links = nchoosek(1:N_Nodes,2); % All node pairs possible
N_Pass=zeros(size(Links,1),1); %Number of pathways between each node pair
for i=1: size(Links,1) %iterating through each node pair
    z=z+1;
    Graph_Temp=Graph;%creating a temporary graph whose edges will be removed in the subsequent steps
    N_Pass(i,1)= min(Degree(Links(i,1),1),Degree(Links(i,2),1)); % maximum number of pathways possible is equal to the minimum of the degree of 2 nodes
    for k = 1 : N_Pass(i,1)
        Pass=  shortestpath(Graph_Temp,Links(i,1),Links(i,2)); %finding the shortest path
        if isempty(Pass)
            break
        else m=m+1;%counting number of pathways
        end
        Graph_Temp= rmedge(Graph_Temp,Pass(1:(size(Pass,2)-1)),Pass(2:(size(Pass,2))));% removing all edges inclued in the first shortest path
        Pass=[];
    end
    N_Pass_Cal(z,1)= m;    
    m=0;
end

Answer 1

[Christine Tobler]

I'd expect the call to rmedge is the most expensive here. You could instead add edge weights for every edge in the graph, and then instead of modifying the graph, just set the weights of the edges you want to remove to Inf instead.

Sorry I probably won't be able to follow up on this answer, I'm just about to head off on vacation.