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

suppose have weighted graph, directed , cyclic. every node has edge directed toward every other node. there no edges connect node itself.

now have source node, , destination node. have start @ source node , traverse n edges , end @ destination node. n arbitrary positive integer (possibly greater number of nodes in graph).

when traverse edge, add our sum (edge weights positive). path take reach our destination node can have cycles. how can maximise our sum?

if not allowed cycles problem np-complete - see https://en.wikipedia.org/wiki/longest_path_problem

assuming allowed paths can include cycles e.g. a,b,c,b,c

for = 1..n compute, each node, length of longest path of length terminates @ node. save length , identity of node before n.

case i=0 path of length 0 previous node null every node.

work out case i+1 case considering, each node, every edge terminating in node.

at end chose node step n longest path terminating @ , use records of previous nodes trace back.

(the above intended compute longest path between 2 nodes because misread question, can modify in beginning extend paths start @ source node, , in end consider paths end @ destination node).

example added after question ab=1,ac=2,bd=10,cd=1 find longest 2-step path d.

i=0 start a

i=1 longest path b length 1, last visited a. longest c length 2, last visited a

i=2 longest length 4 last visited c. longest d 11 last visited b (max of 1+10 b , 2+1 c).

we wanted length 2 stop here , take answer computed d.