Is it worth it to trim a graph as desired before applying a Dijkstra algorithm on that?
Question
I am using Dijkstra algorithm in a program. Suppose I have a graph with vertices and edges. If we imagine all the edges starting from source vertex "a" are as below
a-->b
a-->c and
a-->d
and all the edges ending to vertex "f" are:
b-->f
m-->f
e-->f
w-->f
what I need to know from the beginning is that, I want the edge a-->b as my starting edge (assume "a" as start point) so do not need to search for the other neighbors of "a" i.e. (a-->c and a-->d)
Also I only want the paths which end to m-->f (assume "f" as the destination) i.e. I do not want the path containing b-->f,m-->f,e-->f,w-->f
So is it a good idea to trim my initial graph as such it doesn't contain these edges and then apply Dijkstra on that?
Actually finding these edges needs some searches. I wonder if it is worth (considering time or CPU usage) doing searches and trimming my graph or there is a better way?
Solution
Why not just search for a path from b
to m
then and add the edges you want after that? If you really need it, you may add a special case to exclude edges containing a
and f
from ever being added to the stack -- you'd have to check if that makes it faster overall, my bet is that it will on small graphs but not on really huge ones (it only changes speed by a constant factor anyways).