Suppose I am given a simple directed non-negative weighted graph G = (V, E) and a subset of vertices X ⊂ V. The graph is in adjacency list representation and the subset X as a list. How do I find an algorithm that computes a shorted path between vertice s,t in the graph that doesn't belong to X, and that whenever the path uses two vertices in X, there's at least a vertice that's not in X between these two vertices? The algorithm should be in O(m+nlogn) time.
I have been thinking about this for a long time but couldn't find an algorithm that's under O(m+nlogn) time, any idea how I can approach this?
Assuming m = |E| and n = |V|.
Dijkstra's algorithm with a Fibonacci heap runs in O(m + n log n). So you want to consider the extra constraint without increasing the final time complexity.
If querying whether a vertex is in X cannot be done in constant time, then you first need to make it so by building a hashset of X in O(n). The subsequent queries using this hashset will run in constant time.
Now, removing from the graph the edges between pairs of vertices in X just adds another O(m). Then, you can run Dijkstra's on this new graph with the edges removed, and the whole thing only takes O(m + n log n) time.