An algorithmic question concerning shortest paths and such.

Question

I have a very, very large graph, and I want to find the shortest path from one vertex to another. The graph is directed and unweighted.

I have considered using some modification of Dijkstra's algorithm, but I usually use that for weighted undirected graphs.

So then my other thought was to use a DFS, since I can treat all the weights as one.

Any suggestions? a

EDIT: Ok, I meant to say BFS, I'm sorry.

Answer 1

Have you tried using A*?

Answer 2

Try a BFS instead.

(Note that Dijkstra's algorithm works perfectly fine for unweighted directed graphs — it just happens that in the unweighted case, doing it smartly is essentially equivalent to a breadth-first search.)