Let's say I have a graph G with N vertices and M edges. Each edge has its length and time (let's say in minutes), which it takes to traverse that edge. I need to find the shortest path in the graph between the vertices 1 and N, which is performed in under T minutes time. Since time is the more valuable resource and we care about traversing the graph in time, and only then with minimal length, I decided to use Dijkstra's algorithm, for which I considered the time of each edge as its weight. I added a vector to store the durations. Thus, the algorithm returns the least time, not the least length. A friend suggested this addition to my code:

int answer(int T) {
    int l = 1;
    int r = M; // a very big number
    int answer = M;
    while (l <= r) {
        int mid = (l   r) / 2;
        int time = dijkstra(mid); // the parameter mid serves as an upper bound for dijkstra and I relax the edge only if its length(not time) is less than mid
        if (time <= T) {
            answer = mid;
            r = mid - 1;
        } else {
            l = mid   1;
        }
    }
    if (best == M) {
        return -1; // what we return in case there is no path in the graph, which takes less than T minutes
    }
    return answer;
}

Here is the dijkstra method (part of class Graph with std::unordered_map<int, std::vector<Node>> adjacencyList member):

int dijkstra(int maxLength) {
        std::priority_queue<Node, std::vector<Node>, NodeComparator> heap;//NodeComparator sorts by time of edge
        std::vector<int> durations(this->numberOfVertices   1, M);
        std::set<int> visited;
        // duration 1->1 is 0
        durations[1] = 0;
        heap.emplace(1, 0, 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 (node.length <= maxLength && durations[node.endVertex] > durations[vertex]   node.time) {
                    durations[node.endVertex] = durations[vertex]   node.time;
                    heap.emplace(node.endVertex, durations[node.endVertex], 0);
                }
            }
            // mark as visited to avoid going through the same vertex again
            visited.insert(vertex);
        }
        // return path time between 1 and N bounded by maxKilograms
        return durations.back();
    }

This seems to work but seems inefficient to me. To be frank, I don't understand his idea completely. It appears to me like randomly trying to find the best answer(because nobody said that the time of an edge is tied proportionally to its length). I tried searching for shortest path in graph with time limit but I found algorithms that find the fastest paths, not the shortest with a limit. Does an algorithm for this even exist? How can improve my solution?

CodePudding user response：

What is this?

int time = dijkstra(mid);

It certainly isnt an implementation of the Dijkstra algorithm!

The Dijkstra algorithm requires the starting node and returns THE shortest path from the starting node to every other.

You are going to need a function that returns all the distinct paths between start and end nodes that take less than T. Then you can search them for the one that is cheapest.

Search graph for all distinct paths from start to end
Discard paths that take more then T
Select cheapest path.

CodePudding user response：

Finding a resource constrained shortest path is NPHard. Most approaches to this problem employ a labelling scheme, which is a specialization of dynamic programming. You could use available libraries to accomplish this. See here for a boost implementation.