首先理解题意，给出无向图，给每一条边定向成为有向无环图，使得最长路的长度最短，这里的最长路长度指最长路上点的个数。如果令 dis_i 表示以 i 号点结尾的最长路的长度，那么最后答案应该为 \max(dis_i)。
首先观察性质，如果 dis_i = dis_j，那么证明 i 和 j 之间没有直接的边，因为根据最长路转移的不等式可知如果设从 i 到 j 有一条边，那么 dis_j \ge dis_i + 1，不符合 dis_i = dis_j，所以不存在从 i 到 j 的边；反之同理。
那么当我们定向完成之后，可以求出对于任意点 i 的 dis_i，那么我们根据 dis_i 的值分层，值相同的分为一层，那么根据上述性质可知，每层点内部无边。为了让最长路最短，那么应该在上述条件下，使得层数最少。
形式化的讲：原问题为找到无向图 G 的一个定向 D，使得 |D| 的值最小，其中 |D| 表示 D 中最长路径的包含的点数，即本题中的长度；新问题为找到 V 的一个分层 K，即把点分为若干个集合，并且每个集合内部无边，使得 |K| 最少，其中 |K| 表示分层的个数。原问题与新问题可证明完全等价。
首先证明，如果 G 有一个定向 D，那么存在 V 的一个分层 K，使得 |D| = |K|，其中运算与上文描述相同。因为 |D| = \max(dis_i)，dis_i 表示为以 i 结尾的最长路所包含的点数，即本题中的长度。由上文证明可得 i 与 j 之间无边与 dis_i = dis_j 等价。那么假设已经确定了一个 G 的定向 D，可以求出对于任意一个点 i 的 dis_i，把所有 dis_i = k 的点 i 放到第 k 个集合中，其中 k \in [1,|D|]，因为每一个集合中互相无边，那么即构成了一个分层 K，且分到的层数 |K|，即集合个数，刚好为 |D|。
其次证明，如果 V 有一个分层 K，那么存在 G 的一个定向 K，使得 |K| \ge |D|，其中运算与上文描述相同。假设存在一个 V 的分层 K，每一层内部都是没有边的且每一层之间存在边，假设把每一层按照不同的 dis 从小到大排序，那么假设两个点 i 和 j 分别位于不同的层且 i 比 j 更靠左，将所有的边向右连，那么最长路在每一层最多选一个点，因此 |D| = \max(dis_i) \le |K|。
最后综合上述证明，假设 K 是最小的分层，那么根据上述结论可以推出，存在一个 G 的定向 D，使得 |D| \le |K|。另一方面，|D| 不可能小于 |K|，因为如果 |D| < |K|，那么根据上述结论可以推出，存在分层 K' 使得 |K'| = |D|，那么 |K'| < |K|，与 K 为最小的分层这个条件相悖，所以 |D| = |K|。