Shortest Distance from Leaf to Root of a Directed tree

Question

Here is a very interesting problem which I have encountered: there is a directed tree in which the weight of each node changes with time and I have to find the distance from the root to some node.

Problem Statement:

• There’s a long queue in front of a ticket counter. Here are the queue considerations.
• There can be max 2 incoming queues merging at a junction point
• There can be only one outgoing queue from any junction point
• There can be multiple junction points & the queues move uni-directionally
• There will be only one final ticket counter point to which all the queues lead
• There are multiple entry points for the fans to reach the counter
• I need to design a system that can suggest to the fans the “Optimal Path” and its “Expected Time" to reach the counter

The expected time to reach the counter from a queue depends on the number of people in that queue plus the number of people in the other queues.

• Time taken to cross the ticket counter and receive the ticket is 1 time unit
• Assume that there is a policeman standing at each junction point whose job is to open the junction gate to send people from the in-queue(s) to the out-queue . If there are multiple in-queues for a junction, the policeman will send fans from each queue one by one alternatively

For example, if there are 2 in-queues containing 3 fans each, the leading person from queue1 will be sent in first, followed by the leading person from queue2, followed by next person from queue1 and so on. It’s an alternate pick between the incoming queues.

Full Problem Statement

For a Given Input

• The first line contains the number of junctions
• The second line contains the number of queues
• The next 'e' lines contain three values: the start junction, the end junction and the number of people on this queue. (This is also the maximum number of people that can stand in this queue.)

Calculate the minimum time for a person to reach the ticket counter who is just about to enter any queue. Also, output the path that he should take to reach the counter in minimum time in the worst case (at each junction point, the policeman starts choosing people from the in-queue other than the one we are calculating the minimum time for).

How can one solve this type of time-varying problem?

For Example:

7
6
1 5 9
2 5 5 
3 6 1
4 6 3 
5 7 7 
6 7 4

Graph Looks Like This:

Ticket counter point: 7

Entry points: 1, 2, 3, 4

• Time required for a person who is just entering the queue from entry point 3: 1 person from queue(3,6) + 2 people from queue(4,6) + 4 people from queue(6,7) + 7 people from queue(5,7) + 1 person from queue(1,5) will go before this person.
  
  

Optimal time = 15

Path is 3 -> 6 -> 7

Answer 1

This problem can be solved by finding the shortest path from each entry node (leaves) to the exit node (root).

In my implementation below I used an adjacency matrix to represent that kind of (directed) graph, but you can think of it as a binary tree (because the problem defined maximum 2 input queues for each junction).

Pseudo-code

int shortestPath(root)
    if (both childs exists)
        return min(shortestPath(node->left),shortestPath(node->right))*2+1
    if (left child exists)
        return shortestPath(node->left)
    if (right child exists)
        return shortestPath(node->right)
    return 0; //no childs

The only difference between a normal shortest path and this problem is that whenever we have two incoming queues, the policeman sends fans from each queue one by one alternatively. Which means that in order to pass that queue it will take double the time +1. The +1 is because we assume that he starts from the longer queue path.

C++ Code

Here is a working C++ code that returns a pair with both the optimal time and its path. In case there are more than one optimal paths it will return only one of them.

const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
  return (a.first < b.first) ? a : b;
}

pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
    vector<pair<int,vector<int>>> childs;
    for (int i=0; i<v; i++){
        if (graph[i][v] != -1){
            pair<int,vector<int>> path = findShortestPath(graph,i);
            path.second.push_back(v+1);
            childs.push_back(make_pair(path.first + graph[i][v], path.second));
        }
    }
    if (childs.size() == 2){
        pair<int,vector<int>> path = min(childs[0],childs[1]);
        return make_pair(path.first*2+1, path.second);
    }
    if (childs.size() == 1){
        return make_pair(childs[0].first,childs[0].second);
    }
    else{
        vector<int> start = {v+1};
        return make_pair(0,start);
    }
}

The time complexity of this code is O(n^2) where n is the number of vertices. You might also be able to implement it in O(n) using adjacency list representation (= binary tree).

---

For completeness, here is also the main for creating the graph from the given input and printing the optimal time and path. See this live test of your example's input

int main()
{
    int n, e;
    cin >> n; //num of vertices
    cin >> e; //num of queues
    vector<vector<int>> graph;

    //initialize graph matrix cells to -1
    graph.resize(n);
    for (int i=0;i<n;i++){
        graph[i].resize(n);
        for (int j=0;j<n;j++)
            graph[i][j] = -1;
    }

    //add edges and their weights
    for (int i=0;i<e;i++){
        int s,d,val;
        cin >> s >> d >> val;
        graph[s-1][d-1] = val;
    }

    //run algorithm
    pair<int,vector<int>> path = findShortestPath(graph, n-1);

    //print results
    cout << path.first << endl;
    for (int i=0;i<path.second.size()-1;i++)
        cout << path.second[i] << " -> ";
    cout << path.second[path.second.size()-1] << endl;

    return 0;
}