Optimal path - best career I am new and I have to develop an algorithm with a 2d integer array as input to compute the best career path.
Lets consider a network with n nodes, which are numbered from $1$ to $n$.
All are connected one to the other. 

To move from node $i$ to node $j$ can have different costs (classical example job changing):


positive value indicates a benefit
negative value indicates a loss 
some steps have a cost of $0$


Each entry of $B[i, j]$  indicates the beneﬁt (or the cost, if negative), of a step from node $i$ to node $j$.

I need to find out the maximal gain of a path from i to j is

$$
G(i, j) = \max { \{ g(p) \mid \text{ p is a path from i to j} \}  }
$$

It is not possible to gain from walking in a cycle.
This means, the values in B must be such that for any path p from a node i to itself, we have $g(p) \leq 0$.

Ex of matrix B: 

$$
\begin{array}{cc}
 0 &amp; 1 &amp; 0 &amp; 1 \\\\
−2 &amp; 0 &amp; 0 &amp; −2 \\\\
 0 &amp; 2 &amp; 0 &amp; 1 \\\\
−3 &amp; −1 &amp; −3 &amp; 0
\end{array}
$$

Hints:

1) Cycles bring no gain. Therefore, the greatest possible beneﬁt of moving
from $i$ to $j$ can be achieved by visiting any intermediate node at most once.

2) Consider the following variant of the problem. Let $G_{aux}(i, j, k)$ be the maximal gain that can be achieved by walking from $i$ to $j$ along a path that uses only the nodes $1, \ldots, k$ as intermediate points. 

The tasks asked:


Explain how $G_{aux}(i, j, k)$ can be used to compute $G(i, j)$. Develop a recurrence for $G_{aux}(i, j, k)$.
Write pseudo-code for algorithms that compute arrays with all values of
$G_{aux}$ and $G$ and explain why your algorithms are correct.


Who can help me with this tasks?
Is the basis of all this task the Floyd-Warshall's algorithm ? right?
Be sure to complete the first task before reading below.

Hint 1:


   What are the conditions necessary to use the Floyd-Warshall's algorithm? Does it match those of your exercise?


Hint 2:


   Well, I think you are ready to write the corresponding pseudo-code :-)