输入：具有G顶点的连接的无向图n。
输出：最小化顶点0, 1, ..., n - 1的线性排序
sum(j - i for i in range(n) for j in range(n) if i < j and (i, j) in G)。
n可能约为1000000，并且边缘的数量将是一个比n大的恒定因子，约为5000000。在稍微更普遍的问题中，边缘可能具有较小的正整数权重。首选精确的解决方案，但不是必需的。
一种方法可能是冒泡排序的一种变体，如果它会减少总和，则会交换元素。但我不确定该算法是否会卡在局部最小值中。
您似乎面临最小线性分配问题。网上有关于该主题的博士学位论文（Seitz, Hanna - Contributions to the Minimum Linear Arrangement Problem），该论文具有可访问的论述（请参阅第27页及其后）。
问题是NP难的。引用的资源报告了最著名的算法O(|E| * 2^|V|)的复杂性（第29页及以下）。它还列出了已知有效（多项式）算法的图类，并讨论了近似方案。
PS：这里不是专家，只是遇到了问题和论文，这似乎是一个很好的起点。