CODEWITHSUNDEEP
algorithmgraph
Rockstar5645
Rockstar5645

Reputation: 4518

Traversing exactly n edges, from source node to destination node, find longest path

Suppose we have a weighted graph, it is directed and cyclic. Every node has an edge directed toward every other node. There are no edges that connect a node to itself.

Now we have a source node, and a destination node. I have to start at the source node and traverse exactly n edges and end up at the destination node. Where n is some arbitrary positive integer (possibly greater than the number of nodes in the graph).

When we traverse an edge, we add it to our sum (edge weights are all positive). Now the path we take to reach our destination node can have cycles. How can we maximise our sum?

Upvotes: 0

Views: 99

Answers (1)

mcdowella
mcdowella

Reputation: 19621

If you are not allowed cycles the problem is NP-complete - see https://en.wikipedia.org/wiki/Longest_path_problem

Assuming that you are allowed paths that can include cycles e.g. A,B,C,B,C

For i = 1..N compute, for each node, the length of the longest path of length i that terminates at that node. Save the length and the identity of the node just before the N.

Case i=0 is just a path of length 0 with previous node null for every node.

Work out case i+1 from case i by considering, for each node, every edge terminating in that node.

At the end chose the node for step N with the longest path terminating at it and use the records of previous nodes to trace back.

(The above was actually intended to compute the longest path between any two nodes because I misread the question, but you can modify it in the beginning to extend only paths which start at the source node, and in the end to consider only paths that end at the destination node).

Example added after question ab=1,ac=2,bd=10,cd=1 find the longest 2-step path from A to D.

i=0 start with A

i=1 longest path to B is length 1, last visited A. Longest to C is length 2, last visited A

i=2 longest to A is length 4 last visited C. Longest to D is 11 last visited B (max of 1+10 from B and 2+1 from C).

We wanted length 2 so we stop here and take the answer computed for D.

Upvotes: 0

Related Questions