Shortest path with constraints on traversing edges

Question

While working on a project I've stumbled upon a graph algorithms problem I haven't been able to solve. The problem is as follows:

You have a directed, weighted graph and want to find the shortest path between a start node and an end node while visiting specified nodes (very much like Find the shortest path in a graph which visits certain nodes). However, along with nodes and edges, this graph also has the notion of "items", which reside at nodes and you "pick up" when you enter that node. Now there is an extra constraint that edges can only be traversed if you have obtained the necessary items, I, for that particular edge. Think of it as a key for a door; you need to obtain a key before being able to pass through the door.

I can only think of brute-force methods that blow up exponentially. Can anyone think of anything better or point me to a place where this problem is solved? Or maybe convince me that this is "hard" (computationally speaking)? Thanks for any help!

Just kind of depends on the game (as you might've guessed this is for traversing through a video game), but I would say on the order of 30-40. — maxnelso, Oct 04 '13 at 19:01
Is there some sort of nice ordering on the items? That is, do the items roughly follow a linear progression? — templatetypedef, Oct 04 '13 at 19:04
Ideally they would (and they often do in most games), but it can't be guaranteed. — maxnelso, Oct 04 '13 at 19:07

score 2 · Accepted Answer · answered Oct 04 '13 at 20:24

2

This problem is NP-HARD to solve optimally. There's a simple reduction from the Hamiltonian path problem:

Put unique items on each vertex of the original graph. Construct an sink vertex connected only to the destination vertex. Let the edge between these two vertices require all of the items.

answered Oct 04 '13 at 20:24

tskuzzy

35,812
14
73
140

tskuzzy is constructing a graph where you *have* to visit every vertex to get from start to finish. Assume every edge has the same weight. If a graph has a Hamiltonian cycle, then that cycle is the optimal solution. If the optimal solution isn't a Hamiltonian cycle, then the graph doesn't have one. Thus if you give me your algorithm, I can use it to solve HC of any graph. – DanielV Oct 05 '13 at 08:27

Micromega · Answer 2 · 2013-10-05T05:16:24.060

1

You can try a modified version of the saving algorithm. It's a heuristic to solve the vehicle routing problem. Maybe you can reverse it and create a pick up function for the wanted keys. It's use for a delivery and shortest path problem.

edited Oct 05 '13 at 05:16

answered Oct 04 '13 at 20:02

Micromega

12,486
7
35
72

Shortest path with constraints on traversing edges

2 Answers2