I would like to write an algorithm which can traverse a graph and hopefully later I can implement it to use for an indoor navigation system.
The graph would come from floor plans of a building and the graph nodes represent the building objects such as doors, corridors, stairs, rooms, etc.
The navigation system will accept different users with different capabilities, these capabilities are stored in user profile. For each individual user (or a group of users of the same type, e.g. staff member) the system returns a path specific to that user/s considering his personal functionality. For example if the user of the system is using a wheelchair the system should exclude all the stair nodes from the path (they will be marked non-traversable). Similarly if in order to enter into an indoor space, the user needs to have a key or be an staff member but he is NOT, the system should mark the node (e.g. the door which requires the key) non-traversable and should search for those paths which don't require these specifics requirements.
This was the first part and here I use a function to check these conditions for a given user. The inputs to this function are a node and a user. If the conditions that are required by the node are NOT fulfilled (means user profile doesn't match the condition required by the node) the function returns false= non-traversable.
If the condition holds true, the node stays isTraversable and will be stored somewhere and will be considered for the final path calculation.
The second part is that I have a list that contains all the nodes that are traversable and now the shortest path will be calculate based on 3 different costs, Energy, time and money. The final cost can be a combination of these costs and it sets the weights for the edges.
My problem is with the first part. I want to know how can I make an algorithm that produces the subgraph (the list with the traversable nodes in it). And later how can I use this algorithm to modify Dijkstra to fit this system.
Can anybody help with writing a pseudocode for the algorithm so that I can understand how would it work in clear steps or any hints on how can I make these steps into pseudocode?
Please note that at this stage the performance is not very important for me.
Best Answer
The usual way to solve that would be instead of doing a preprocessing step before running Dijkstra, just run Dijkstra and give all the non-traversable edges a really high weight. That way you avoid preprocessing any nodes that are definitely not in the shortest path, and also you avoid the problem of not finding a path that may actually be shorter, but came later when you search by the order of children.
You might also consider A* if your weights are distances. It's more efficient in eliminating nodes you don't need.