algorithm - 有向树的叶子到根的最短距离

Question

这是我遇到的一个非常有趣的问题:有一个有向树，其中每个节点的权重随时间变化，我必须找到从根到某个节点的距离。

问题陈述:

• 售票柜台前排起了长队。这是队列考虑因素。
• 最多可以有 2 个传入队列在交汇点合并
• 从任何交汇点只能有一个出站队列
• 可以有多个交汇点，队列移动单向
• 只有一个最后的售票柜台，所有的队列领先
• 粉丝有多个入口点可以到达柜台
• 我需要设计一个系统，可以向粉丝推荐“最优路径”及其到达柜台的“期望时间”

从队列中到达柜台的预期时间取决于该队列中的人数加上其他队列中的人数。

• 穿过售票柜台并领取门票所需的时间为 1时间单位
• 假设每个交界处都有一名警察站着谁的工作是打开路口门派人从入队列到出队列。如果一个队列有多个路口，警察会把每个队列的粉丝一一送走或者

例如，如果有 2 个队列，每个队列包含 3 个粉丝，则 queue1 的领头人将首先被派出，然后是 queue2 的领头人，然后是 queue1 的下一个人，依此类推。这是传入队列之间的替代选择。

Full Problem Statement

对于给定的输入

• 第一行包含路口数
• 第二行是队列数
• 接下来的 'e' 行包含三个值:起点交汇点、终点路口和队列中的人数。 (这也是这个队列中可以站的最大人数。)

计算一个人到达售票柜台的最短时间，他正要进入任何队列。此外，输出在最坏情况下他应该在最短时间内到达柜台的路径(在每个交汇点，警察开始从队列中选择我们正在计算的人以外的人的最短时间)。

如何解决这类时变问题？

例如:

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

图表如下所示:

售票点:7

入口点:1、2、3、4

• 刚进入队列的人从入口开始所需的时间第 3 点:队列中的 1 人 (3,6) + 队列中的 2 人 (4,6) + 4来自队列 (6,7) 的人 + 来自队列 (5,7) 的 7 人 + 来自队列 (5,7) 的 1 人queue(1,5) 将排在这个人之前。
  
  

最佳时间 = 15

路径是 3 -> 6 -> 7

Answer 1

这个问题可以通过找到从每个入口节点(叶子)到导出节点(根)的最短路径来解决。

在我下面的实现中，我使用邻接矩阵来表示这种(有向)图，但您可以将其视为二叉树(因为问题为每个连接点定义了最多 2 个输入队列)。

伪代码

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

正常 最短路径与这个问题的唯一区别是，每当我们有两个 传入队列时，警察就会交替地从每个队列中逐一发送粉丝。这意味着为了通过该队列，需要两倍的时间 +1。 +1 是因为我们假设他从较长的队列路径开始。

C++代码

这是一个有效的 C++ 代码，它返回一对最佳时间及其路径。如果有多个最佳路径，它将只返回其中一个。

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);
    }
}

这段代码的时间复杂度是O(n^2)，其中n是顶点的数量。您也可以使用邻接列表表示法(= 二叉树)在 O(n) 中实现它。

---

为了完整起见，这里还有 main，用于根据给定的输入创建图形并打印最佳时间和路径。 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;
}