Est-il la peine de rogner un graphique comme vous le souhaitez avant d'appliquer un algorithme de Dijkstra à ce sujet?

Question

J'utilise l'algorithme Dijkstra dans un programme. Supposons que j'ai un graphe dont les sommets et les arêtes. Si l'on imagine tous les bords à partir de sommet source "a" sont comme ci-dessous

a-->b        
a-->c   and  
a-->d  

et tous les bords se terminant au sommet "f" sont les suivants:

b-->f
m-->f
e-->f
w-->f

ce que je dois savoir dès le début est que, je veux le bord -> b comme mon bord de départ (en supposant "a" comme point de départ) alors ne pas besoin de rechercher les autres voisins de "a" à savoir (a-->c and a-->d)

Je veux aussi que les chemins qui se terminent à m -> f (on suppose "f" comme destination) à savoir que je ne veux pas le chemin contenant b-->f,m-->f,e-->f,w-->f

Alors, est-ce une bonne idée de couper mon graphique initial en tant que telle ne contient pas ces bords, puis appliquer Dijkstra à ce sujet?

En fait de trouver ces bords a besoin de quelques recherches. Je me demande si cela vaut la peine (en tenant compte du temps ou l'utilisation du processeur) faisant des recherches et parage mon graphique ou il y a une façon meilleure?

Answer 1

Pourquoi ne pas chercher juste pour un chemin de b à m puis et ajoutez les bords que vous voulez après? Si vous avez vraiment besoin, vous pouvez ajouter un cas particulier d'exclure les bords contenant a et f jamais d'être ajouté à la pile - vous auriez à vérifier si cela le rend plus rapide dans l'ensemble, mon pari est que cela graphiques sur les petits mais pas sur ceux qui sont vraiment énormes (il ne change que la vitesse d'un facteur constant de toute façon).