3
$\begingroup$

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 benefit (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 benefit 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:

  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?

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

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 :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.