'Get maximum value one can achieve by traversing nodes in a directed graph
The attached diagram visually presents data in a particular way, illustrating a pyramid with a value assigned to each node, and arrows indicating the paths one may take to traverse the pyramid to accumulate points.As one traverses the pyramid they collect the values in the nodes they pass. I would like to know what is the maximum value one can achieve by traversing these nodes.I have a data as a stream of integers, or if you prefer you can think of the input as an array of integers. So in the example sketched in the diagram, your input is 40, -10, 25, 75, -30, -5, -15, 20, 120, 100. The first element populates the node at the top of the pyramid. The second element occupies the leftmost node in the second row of the pyramid. The elements snake around the pyramid, filling rows from left to right. The input is guaranteed to complete a pyramid.
Rules for accumulating points: The value in a node can only be counted once per path From each node you can reach two nodes, unless you've reached a node that has no leaves, indicating the end of a path. Image of the graph
Solution 1:[1]
You can move the value from the node to the incoming edges.
If you invert the sign of the values (*(-1)) then you can simply apply the Bellman-Ford algorithm on each final node for finding the shortest path. Dijkstra won't work because there are negative edges. Take the lowest result you can get.
The result of the shortest path needs to inverted again. Finally, we lost the value from the tip of the pyramid (has no incoming node). We need to add this onto that value and should obtain the answer.
It is not an optimal solution, but it would run inside O(sqrt(|V|)|V||E|)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |