a bit of uva: UVa 104 - Arbitrage

Problem Statement:
UVa 104 - Arbitrage

Summary:
Given an adjacency matrix, find the shortest cycle such that the product of the edges is bigger than 1.01

I was stuck on this problem for a while (I sincerely think that this question is difficult! haha) because a lot of people said they solved this problem simply by running Floyd-Warshall on the graph. However, I really don't think that the implementation is that obvious. Eventually, I learnt a way to solve the problem, it resembles Floyd-Warshall, but not exactly the same. It borrows the main idea that we can incrementally build an optimal path by considering k = 1,2,...,N one by one.

The idea is this:
Suppose we are given a path with \(m\) edges for each pair of vertices \( (i,j) \)such that the product of the edges is maximum (in other words, the optimal path using \(m\) edges). Then to find the optimal path between \(i,j\) using \(m+1\) edges can be done by trying all \(k = 1,2,3,\ldots, N\) and choose \(k\) such that the path i-k-j (where i-k has \(m\) edges, k-j is a direct edge\) is optimal. That means, we take D[i][j][m+1] = max of ( D[i][k][m] * D[k][j][1] ) for k = 1,2,...,N. Now it remains to prove that the path we found is indeed optimal, and the proof is by contradiction. Suppose that there is \(p\) = i-k'-j (where i-k' has m edges, k'-j is a direct edge) with \(k' \neq k\) such that the product of its edges are larger than that of i-k-j. Furthermore, suppose that \(q\) is the path i-k'-j such that i-k' is the optimal path using m edges. Then we have: product of edges of \(p\) \(\leq\) product of edges of \(q\) < product of edges of i-k-j, contradiction. Therefore i-k-j found must have been optimal.

As such we can solve the problem by iterating through m starting from m = 2, with the initial condition of m=1 which is the initial adjacency matrix. We also need to maintain a path matrix to reconstruct the path found. This is done by storing the information about the parent of j in a path between i and j: At first, every parent of j is i for all i-j. During the progress of the algorithm, if i-k-j is larger than i-j, update par[i][j] = k (since the parent of j is now k).

Implementation:

void floyd(){
   for(int s=1;s<N;++s) //0 indexed
      for(int k=0;k<N;++k)
         for(int i=0;i<N;++i)
            for(int j=0;j<N;++j){
               double temp = arb[i][k][s-1]*arb[k][j][0];
               if(temp > arb[i][j][s]){
                  arb[i][j][s] = temp;
                  par[i][j][s] = k; //since par[k][j][0] = k
               }
            }
}