Rather than using the graphshortestpath function from Bioinformatics Toolbox, I recommend creating a graph or digraph object from your sparse adjacency matrix and using the shortestpath function for graph and digraph objects. You can do a lot with graph and digraph objects; see the documentation for a list of functions that can work on these objects.
To remove edges connected to a node, you can use outedges (and inedges if your network is a digraph) then call rmedge. Let's create a graph using the Buckyball data and display it.
G = graph(bucky);
f1 = figure;
p1 = plot(G);
title('Full bucky graph');
Now let's remove all edges connected to node 17 and plot the resulting graph.
edgesConnectedTo17 = outedges(G, 17);
Gm17 = rmedge(G, edgesConnectedTo17);
p2 = plot(Gm17);
title('Bucky graph minus edges connected to 17')
Both plots display all 60 nodes of the bucky graph but they have different layouts. Since node 17 isn't connected to anything in the second plot, it's displayed off to the side. The layout differences does make it a little difficult to compare the two plots. Let's make one more plot.
f3 = figure;
p3 = plot(Gm17, 'XData', p1.XData, 'YData', p1.YData);
title('Bucky graph minus edges connected to 17, nodes in the same place')
To keep node 17 (and the rest of the nodes) in the same place as in the first plot, the third plot uses the node coordinates from the first. If you quickly switch between the first and third figure, the only differences should be the title, the three edges that are present in the first but not the third, and the tick labels on the axes (which are present because I explicitly specified coordinates when I created the third plot.) As a warning, the code below will flicker quite a bit.
for k = 1:1000