Up front -- this is related to a class project that I'm doing so I'm not looking for complete answers (because that would be cheating) -- I'm just looking to get some opinions on high-level stuff because I know there are a few computer scientists here.

Let's say you have a typical graph with weighted edges and you need to find the shortest path from the source node to a given target node (aka Dijkstra's Algorithm). In this graph, though, certain edges are "locked", and you need a key to traverse them. Keys are found by visiting nodes. So now, to find the shortest path, you need to take into account which nodes to visit to collect keys (if any, since it might cost more to pick up a key and then traverse a locked edge than to go "around" the locked edge in the first place). There is no set pattern to where locked edges and their respective keys are. One key can open many locks.

I was thinking of doing this with a modified Dijkstra's (using mirrors/copies of the graph and jumping between them through zero-weight edges), but my implementation would be incredibly incredibly inefficient (exponential complexity). Do you guys think that there's a better algorithm than Dijkstra's to use, or should I look into finding a more efficient implementation with Dijkstra's?

If there is no pattern to where locked edges and the keys are, I don't see how this can be anything other than exponential or factorial time. I suppose you could do is use a heuristic to guess where the keys or or try to find patterns.

yeah, factorial time.

Okay that's what I thought I looked at my crappy implementation again and I can see how it would be factorial time (number of locked edges factorial)

Thanks for the reassurance