Стоит ли обрезать график по желанию, прежде чем применять алгоритм Дейкстры на этом?

Question

Я использую алгоритм Дейкстры в программе. Предположим, у меня есть граф с вершинами и ребрами. Если представить, что все ребра, начиная с исходной вершины "a" , будут такими, как показано ниже

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

и все ребра, заканчивающиеся вершиной "f" :

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

Что мне нужно знать с самого начала, так это то, что я хочу, чтобы ребро a -> b было моим начальным ребром (предположим, "a" в качестве начальной точки), поэтому не нужно искать других соседей "a" т.е. (a-->c and a-->d)

Кроме того, я хочу только пути, которые заканчиваются на m -> f (в качестве пункта назначения укажите "f" ), т.е. я не хочу путь, содержащий b-->f,m-->f,e-->f,w-->f

Так что это хорошая идея, чтобы обрезать мой исходный граф, чтобы он не содержал эти ребра, а затем применить Dijkstra к этому?

На самом деле нахождение этих ребер требует некоторых поисков. Интересно, стоит ли (учитывая время или использование процессора) выполнять поиск и обрезать мой график, или есть лучший способ?

Answer 1

Почему бы просто не найти путь от b до m, а затем добавить нужные ребра после этого?Если вам это действительно нужно, вы можете добавить специальный случай, чтобы исключить добавление ребер, содержащих a и f, в стек - вам нужно проверить, ускоряет ли это в целом, моя ставка таковабудет на небольших графиках, но не на действительно огромных (в любом случае скорость меняется только на постоянный коэффициент).