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

Question

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

问题陈述：

售票柜台前排起了长队。这是队列注意事项。
最多可以有 2 个传入队列在交汇点合并
任何交汇点只能有一个出站队列
可以有多个交汇点，队列移动单向
只有一个最后的售票点，所有的队列领先
粉丝有多个入口点可以到达计数器
我需要设计一个可以向粉丝建议的系统 “最佳路径”及其到达柜台的“预期时间”

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

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

例如，如果有2个in-queue，每个队列有3个fans，则queue1的领头人将首先被送入，然后是queue2的领头人，然后是queue1的下一个人，依此类推。这是传入队列之间的替代选择。

Full Problem Statement

对于给定的输入

第一行包含路口数
第二行包含队列数
接下来的 'e' 行包含三个值：起点交叉点、终点路口和队列中的人数。（这也是这个队列最多可以站多少人。）

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

如何解决这种时变问题？

例如：

图表如下所示：

售票点：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

这应该用动态规划来解决。
令 P(j) 为人的位置，如果它采用最优扇形，则通过连接点 j。例如在你的情况下 P(6) = 4，因为到达交界点 3 的人将是第 4 个通过交界点 6 的人（在 P27、P26 和 P28 之后）。
下面三个命题显而易见，解决问题。
如果 a "junction point" j 是粉丝 , P(j) = 1 (base case)
如果 "junction point" j 是与 children l 和 r 的正确交汇点，并且在 l 和 j 之间的队列中有 x 个人，在 r 和 j 之间的队列中有 y 个人，我们有 P( j) = 2 * min( P(l) + x , P(r) + y)
如果有人第n次通过柜台，则需要n-1次才能到达那里。
您可以使用 DP 轻松获得时间并进行一些簿记（如果在左侧或右侧达到最小值），您可以确定哪个是最佳风扇。

Answer 2

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

在我下面的实现中，我使用邻接矩阵来表示那种（有向）图，但您可以将其视为二叉树（因为问题为每个连接点定义了最多 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++ 代码，return 与最佳时间及其路径成对。如果有多个最佳路径，它将 return 只有其中一个。

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

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

Shortest Distance from Leaf to Root of a Directed tree

algorithm

tree

graph

shortest-path

售票点：7

入口点：1、2、3、4

最佳时间 = 15

路径是 3 -> 6 -> 7

伪代码

C++代码