# 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 & 1 & 0 & 1 \\\\ −2 & 0 & 0 & −2 \\\\ 0 & 2 & 0 & 1 \\\\ −3 & −1 & −3 & 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.

1. Explain how $G_{aux}(i, j, k)$ can be used to compute $G(i, j)$. Develop a recurrence for $G_{aux}(i, j, k)$.

2. 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?

• This looks quite a bit like homework, so I added a tag. – Pedro May 22 '12 at 19:59
• It is an exercise given at the class – Patric May 22 '12 at 20:02
• The example matrix violates the "no positive cycles" condition; the cycle $2\to 3\to 2$ has gain 2. – JeffE May 23 '12 at 8:19