Two pawns walking in a complete graph We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices.
At the beginning we have two pawns in $v_1$. You can move pawns by following these rules:


*

*Every time you move only one pawn

*pawn standing on $v_i$ can only go to $v_j$ iff $j \ge i$ - (so it can only move to a vertex which is further than it in $C$)

*Every vertex has to be visited by at least one pawn

*After the last move both pawns should be standing in $v_n$


Whats the optimal algorithm determining the smallest sum of visited edges?
 A: Given weights $w(i,j)$ of edges $v_iv_j$.
For $1\le i\le j\le n$ let $F(i,j)$ denote the minimal sum of a valid move sequence of the pawns from $(v_1,v_1)$ to $(v_i,v_j)$ such that $v_1,\ldots v_j$ have been visited.
Then we have
$$\tag1F(j,j)=\min\{F(i,j)+w(i,j)\mid 1\le i<j\}$$
and
$$\tag2\begin{align}F(i,j)=\min\bigl\{&F(i,j-1)+w(j-1,j),\\&\min\{\,F(k,j)+w(k,i) \mid 1\le k<i\,\}\bigr\}\end{align}$$
if $i<j$. We can view $(1)$ as special case of $(2)$ if we agree that 
with $F(i,j-1)+w(j-1,j)=+\infty$ if $i=j$.
We are looking for $F(n,n)$.
Computing all $F$ values takes $O(n^3)$.
(It is certainly not possible to be faster than $O(n^2)$ because it is necessary to look at almost each edge weight at least once)

An improvement over the above is to do an $A^*$ search: Let $Q$ be a priority queue for entries of  $(i,j,s)$ with $i,j\in\{1,\ldots,n\}$ and $s\ge0$, ordered by $s$, and let $A$ an array.


*

*Initally, set $A(i,j)\leftarrow0$ for $1\le i\le j\le n$. Insert $(1,1,0)$ into $Q$.

*Pop $(i,j,s)$ with minimal $s$ from $Q$.

*If $i=j=n$, terminate with $s$ as result

*If $i>j$, swap $i\leftrightarrow j$.

*If $A(i,j)=1$ go back to step 2.

*Set $A(i,j)\leftarrow 1$. For $i+1\le k\le \min\{j+1,n\}$, insert $(k,j,s+w(i,k))$ into $Q$

*If $j<n$, insert $(i,j+1,s+w(j,j+1))$ into $Q$

*Go back to step 2


With a suitable priotrity queue structure (e.g. Fibonacci heap), better bookkeeping about duplicate entries in the queue, and usage of the decrease-key operation, this algorithm should have running time $O(n^2\log n)$.
