Shortest path algorithm in graph for queries

Question

I have a weighted undirected Graph. Its vertices are part of two sets - S and T. Firstly, the edges are entered. Then it's specified which vertices are part of the T set (the rest are part of the S set). Then q queries follow. For every query(consists of a source vertex), the program must print the shortest path between the specified source vertex and any vertex of the set T.
I implemented the program using Dijkstra's algorithm. I call it for each query on the source vertex(dijkstra returns the distance between source and all other vertices) and then return the minimum of these numbers.

const int M = 1000000;
std::unordered_set<int> T;
class Node {
public:
    int endVertex;  // stores the second vertex of the edge
    int weight;     // stores the weight required, it is the weight of the edge
    Node(int end, int weight) {
        this->endVertex = end;
        this->weight = weight;
    }
};

struct NodeComparator {
    bool operator()(const Node &first, const Node &second) {
        return first.weight > second.weight;
    }
};


class Graph {
private:
    std::unordered_map<int, std::vector<Node>> adjacencyList; // it's a vector because there may be repeated Nodes
    int numberOfVertices;

    std::vector<int> dijkstra(int source) {
        std::priority_queue<Node, std::vector<Node>, NodeComparator> heap;
        std::vector<int> distances(this->numberOfVertices, M);
        std::unordered_set<int> visited;
        // distance source->source is 0
        distances[source] = 0;
        heap.emplace(source, 0);
        while (!heap.empty()) {
            int vertex = heap.top().endVertex;
            heap.pop();
            // to avoid repetition
            if (visited.find(vertex) != visited.end()) {
                continue;
            }
            for (Node node: adjacencyList[vertex]) {
                // relaxation
                if (distances[node.endVertex] > distances[vertex] + node.weight) {
                    distances[node.endVertex] = distances[vertex] + node.weight;
                    heap.emplace(node.endVertex, distances[node.endVertex]);
                }
            }
            // mark as visited to avoid going through the same vertex again
            visited.insert(vertex);
        }
        return distances;
    }

    int answer(int source) {
        std::vector<int> distances = this->dijkstra(source);
        std::set<int> answer;
        for (int i: T) {
            answer.insert(distances[i]);
        }
        return *answer.begin();
    }
// other methods
};
// main()

However, my solution does not pass half the tests due to timeout. I replaced my dijkstra method with a Floyd-Warshall algorithm, which directly overrides the starting adjacency matrix, because I thought that the method would be called only once, and then each query would just find the minimum element in the source line of the matrix. This time the timeouts are even worse.

Is there a specific algorithm for efficient queries on shortest path? How can I improve my algorithm?

Answer 1

So, it turns out the problem needs to be solved in such a way, which calculates the result only once, instead of for each query, as I did previously. The solution is to add a fake vertex, which is connected to all vertices in the T set, and the weight of each of those edges is zero. Then, you have to do std::vector<int> distances = graph.dijkstra(this fake edge); and the answer of each query is distances[query].

Answer 2

This seems unnecessary

std::unordered_set<int> visited;

A normal vector does the job faster

std::vector<int> visited(numberOfVertices,0);

so you can replace

if (visited.find(vertex) != visited.end()) {

with the much faster

if( visited[vertex] )

and also

visited.insert(vertex);

becomes

visited[vertex] = 1;

---

Individual queries can be sped up

replace

    std::set<int> answer;
    for (int i: T) {
        answer.insert(distances[i]);
    }
    return *answer.begin();

with

int shortest = MAX_INT;
for (int d: distances) {
   if( d < shortest ) {
      shortest = d;
   }
}
return shortest;

---

Modify your dijsktra code to stop searching on a path when it reaches a T node - no need to go any further.

Answer 3

You can reverse all edges and find the shortest path from the set of T (run Dijkstra from all T vertices together) to some vertex S. And precalculate all distances to each S and answer to query in O(1).