Given a directed graph $G=(V, E)$ where $V=\{1,2,...,n\}$ and a weight function $w:E\rightarrow\Bbb{Z}^+$, for every permutation $\pi$ of $V$ we will define its backwards-weight as $$ bw(\pi) = \sum _{\substack{1\le i,j\le n \\ \pi(j)\lt\pi(i) \\ (i, j)\in E}} w(i,j) $$ For example, given this weighted graph: The graph $G=(\{1,2,3\},\{(1,2),(1,3),(2,3),(3,1)\})$ with the weights $w=\begin{pmatrix}(1,2)&(1,3)&(2,3)&(3,1)\\3&2&1&5\end{pmatrix}$, the permutation $\pi=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}$ has a backwards-weight of $bw(\pi)=w(1,2)+w(3,1)=3+5=8$: A visual representation of the permutation and its backwards-weight
I wish to find a permutation with the minimum backwards-weight. If there is a topological sort for the graph then I'm finished, but for most cases, there won't be, hence why this problem is called The Almost-Topological Sort.
My first instinct is to define a weight for each node $v$, by summing the weights of all the edges that $v$ is its tail: $w(v)=\sum_{v\neq u\in V}w(v,u)$, and sort the nodes based on their weight.
This problem is known as the Feedback Arc Set problem, and is shown to be $NP$-complete (in it's decision version). This is one of the Karp's 21 $NP$-complete problems. A consequence is that there is no known efficient algorithm to this problem.
You can still solve the problem with brute-force, branch & bound or something more sophisticated, or you can rely on heuristics to find good approximate solutions.