I don't have a great use case for this myself, but it seems like it should be possible to run bidirectional dijkstra with two threads.