How to restrict shortest path - dijkstra algorithm with maximum cost?

I am wondering how I can assign a maximum cost value for the shortest path problem. In my problem, I have risks associated with nodes. So I would like to minimize risk, but while 开发者_StackOverflow社区doind that I want it to find a solution with limited number of nodes.(eg. find minimum risk from node A to node B, while ensuring solution does not exceed n number of nodes) Thanks a lot.

Dijkstra is Best First Search, i.e. we should be sure, that distance to the best node never will become better. It works for minimum-Dijkstra with non-negative edges. In general case you can use Ford-Bellman. In case you want to use not more than n vertexes, i can suggest you Dynamic programming dp[vertex][used_vertex_count] with complexity O(|V| * n) states and memory and O(|E| * n) time. Or create adjacency matrix of the graph with zeros on main diagonal and infinity insted of absent edge and calc it's n exponent. a_{ij} will be min path from i to j using no more than n vertexes.

I think that some algorithm that involves heuristics would be best suited here, the heuristic being a notion of how "close" to the goal you are at each step, and which node will take you closer to the goal. Without that, I think we would need to run an exponential algorithm in the worst case (which would be when the goal cannot be reached using just n nodes. In this case, we will look at all paths that use n nodes before we conclude that the problem cannot be solved).

One example of using a non-heuristic algorithm is this: Run Dijkstra's in a regular fashion selecting the node with min risk. Along the way, keep track of the number of nodes you have visited. If the number of nodes goes beyond n then abandon your current route and backtrack to a previous node and use the node with the next lowest risk. Naturally, you can't backtrack just one level above n, since if the goal were in the next level, it would have been picked. Therefore, you backtrack to level n-2 and carry on. This too will be exponential as there isn't a real way to determine non-existence without checking all paths.

It could also be that I'm missing something.

You want to use Prim's algorithm because it finds all minimal spanning tree in the given graph. Then it is easy to select the mst with the desired constraint.