CODEWITHSUNDEEP
algorithmpathgraph-algorithmpath-finding
arg
arg

Reputation: 61

Path finding algorithm on graph considering both nodes and edges

I have an undirected graph. For now, assume that the graph is complete. Each node has a certain value associated with it. All edges have a positive weight. I want to find a path between any 2 given nodes such that the sum of the values associated with the path nodes is maximum while at the same time the path length is within a given threshold value. The solution should be "global", meaning that the path obtained should be optimal among all possible paths. I tried a linear programming approach but am not able to formulate it correctly. Any suggestions or a different method of solving would be of great help.

Thanks!

Upvotes: 4

Views: 1187

Answers (4)

Dr. Hans-Peter Störr
Dr. Hans-Peter Störr

Reputation: 26006

If you just add the weight of a node to the weights of its outgoing edges you can forget about the node weights. Then you can use any of the standard algorigthms for the shortest path problem.

Upvotes: 0

zzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzz

Reputation: 1

Integer program (this may be a good idea or maybe not):

For each vertex v, let xv be 1 if vertex v is visited and 0 otherwise. For each arc a, let ya be the number of times arc a is used. Let s be the source and t be the destination. The objective is

maximize ∑v value(v) xv .

The constraints are

∑a value(a) ya ≤ threshold ∀v, ∑a has head v ya - ∑a has tail v ya = {-1 if v = s; 1 if v = t; 0 otherwise (conserve flow)
∀v ≠ x, xv ≤ ∑a has head v ya (must enter a vertex to visit)
∀v, xv ≤ 1 (visit each vertex at most once)
∀v ∉ {s, t}, ∀cuts S that separate vertex v from {s, t}, xv ≤ ∑a such that tail(a) ∉ S ∧ head(a) ∈ S ya (benefit only from vertices not on isolated loops).

To solve, do branch and bound with the relaxation values. Unfortunately, the last group of constraints are exponential in number, so when you're solving the relaxed dual, you'll need to generate columns. Typically for connectivity problems, this means using a min-cut algorithm repeatedly to find a cut worth enforcing. Good luck!

Upvotes: 0

aelguindy
aelguindy

Reputation: 3711

This might not be perfect, but if the threshold value (T) is small enough, there's a simple algorithm that runs in O(n^3 T^2). It's a small modification of Floyd-Warshall.

d = int array with size n x n x (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 assumes that the paths are allowed to be not simple, they can contain cycles.

EDIT2: This also assumes that if a node appears more than once in a path, it will be counted more than once. This is apparently not what OP wanted!

Upvotes: 1

Saeed Amiri
Saeed Amiri

Reputation: 22565

If you looking for an algorithm in general graph, your problem is NP-Complete, Assume path length threshold is n-1, and each vertex has value 1, If you find the solution for your problem, you can say given graph has Hamiltonian path or not. In fact If your maximized vertex size path has value n, then you have a Hamiltonian path. I think you can use something like Held-Karp relaxation, for finding good solution.

Upvotes: 1

Related Questions