patternMinor
Optimal path - best career
Viewed 0 times
careerpathoptimalbest
Problem
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):
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:
-
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?
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:
-
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?
Solution
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 :-)
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 :-)
Context
StackExchange Computer Science Q#2005, answer score: 4
Revisions (0)
No revisions yet.