Algorithm for finding a trajectory on a graph taking into account both nodes and edges

Question

I have an undirected graph. For now, suppose the schedule is complete. Each node has a specific value associated with it. All ribs are positive weight. I want to find the path between any two given nodes, so that the sum of the values ​​associated with the nodes of the path is maximum, and at the same time, the path length is within the given threshold value. The solution must be "global", which means that the resulting path must be optimal among all possible paths. I tried the linear programming approach, but I can not formulate it correctly. Any suggestions or other method of solution will be very helpful.

Thanks!

Answer 1

This may not be ideal, but if the threshold value (T) is small enough, there is a simple algorithm that works in O (n ^ 3 T ^ 2). This is a small modification of Floyd-Warsall.

d = int array with size nxnx (T + 1) initialize all d[i][j][k] to -infty for i in nodes: d[i][i][0] = value[i] for e:(u, v) in edges: d[u][v][w(e)] = value[u] + value[v] for t in 1 .. T for k in nodes: for t' in 1..t-1: for i in nodes: for j in nodes: d[i][j][t] = max(d[i][j][t], d[i][k][t'] + d[k][j][t-t'] - value[k]) The result is the pair (i, j) with the maximum d[i][j][t] for all t in 0..T 

EDIT: this suggests that paths are not just allowed, they can contain loops.

EDIT2: This also assumes that if a node appears more than once in a way, it will count more than once. Apparently this is not what the OP needs!

Answer 2

If you are looking for an algorithm in the general graph, your problem is NP-Complete, suppose the path length is n-1 and each vertex has a value of 1 . If you find a solution to your problem, you can say the given graph has a Hamiltonian trajectory or not. In fact, if your maximum vertex size path is n , then you have a Hamiltonian path. I think you can use something like a Held-Karp vacation to find a good solution.

Answer 3

The whole program (this might be a good idea or maybe not):

For each vertex v, let x _v be equal to 1 if the visited vertex is v and 0 otherwise. For each arc a, let y _a be the number of times that arc a is used. Let s be the source and t be the destination. The goal is

maximize & sum; _v value (v) x _v .

Limitations

& sum; _a value (a) y _a & le; threshold? forall; v, & sum; _{a has a head v} y _a - & sum; _{a has a tail v} y _a = {-1 if v = s; 1 if v = t; 0 otherwise (save stream)
? forall; v & ne; x, x _v ? & sum; _{a has a head v} y _a (you must enter a vertex to visit)
? forall; v, x _v ? 1 (visit each vertex no more than once)
? forall; v & notin; {s, t},? forall; the cuts S that separate the vertex v from {s, t}, x _v & le; & sum; _{a such that tail (a) & notin; S & wedge; head (a) & in; S} y _a (use only vertices, not on isolated loops).

To solve, keep a branch and associate it with relaxation values. Unfortunately, the last group of constraints is exponential in number, so when you decide a relaxed double, you need to create columns. Typically, for connection problems, this means that the minimum cut algorithm is used repeatedly to find a shortcut that needs to be followed. Good luck

Answer 4

If you simply add the weight of a node to the weight of its outgoing edges, you can forget about the weight of the node. Then you can use any of the standard algorithms for the shortest path .