Two pawns walking in a complete graph

Question

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?

Answer 1

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.

1. Initally, set $A(i,j)\leftarrow0$ for $1\le i\le j\le n$. Insert $(1,1,0)$ into $Q$.
2. Pop $(i,j,s)$ with minimal $s$ from $Q$.
3. If $i=j=n$, terminate with $s$ as result
4. If $i>j$, swap $i\leftrightarrow j$.
5. If $A(i,j)=1$ go back to step 2.
6. 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$
7. If $j<n$, insert $(i,j+1,s+w(j,j+1))$ into $Q$
8. 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)$.