Which of the following options take less processing time/is less expensive in a graph traversal algorithm for a (indoor)navigation system?

a) To produce all possible paths between start and destination points (nodes on the graph) then applying a filtering mechanism to match the navigation user's capabilities and preferences (such as finding all the paths on the graph and then exclude stairways for wheelchair users), or

b) As soon as the user's profile is available to the system, filter the graph and exclude the paths which are non-traversable for this user and then run a shortest path algorithm?

  • That depends on the cost of user-path filtering vs the cost of path finding. – Wilbert Dec 13 '13 at 16:55
  • There are all sort of constraints defined for the user of the navigation system that should be matched with indoor space constraints, and time of using the system (this is the second choice). The first one is more like a pre-processing sort of path-finding. – NKK Dec 13 '13 at 17:02

It seems to me to me that your user-matching removes a few nodes from the graph and changes the cost of others. That is, preferences make some paths cheaper (better), and actually modifies the graph itself (removal of stair nodes for wheelchair users).

That means that you need to run shortest-path on the modified graph to get the result at all - only b) will work. The precomputed version a) does not take into account the preference-changed path costs and removed nodes and therefore will give you wrong answers.

| improve this answer | |
  • Yes the second approach will produce a subgraph first- based on constraints and user preferences- and then applies the shortest path algorithm to find the best match. The first approach(a), calculates ALL the possible paths between the two nodes, and then in this new subgraph it will match the user profile to exclude the non-traversable paths from the search, and then return the best match. – NKK Dec 13 '13 at 18:11
  • Yes, but to get the best path, you obviously need to put a cost on each edge. The precomputed version will have wrong costs, because some of those costs will be part of the user's prefs, and not globally valid. – Wilbert Dec 20 '13 at 11:19

Instead of filtering the graph to remove paths why don't you add weights to the nodes or edges and then implement your shortest path algorithm so that it is simply unable to traverse nodes above some configurable weight threshold.

Depending on how complicated your constraints are, you could also modify the algorithm to check sets of constraints as it traverses the graph. Basically, what I'm trying to say is that you can filter to ignore unsuitable nodes as part of your shortest path algorithm, you really don't need to do this in two steps.

| improve this answer | |
  • my thoughts exactly, leave the Graph as-is but use an algorithm that is cost aware and use a very high cost value for the nodes / path that are not usable for a given user. Then you could integrated these costs as either one a preprocessing of the Graph to integrate costs as payload or through a look up table associating Graph entities with user / costs and have the algorithm fetch the info through there – Newtopian Dec 13 '13 at 18:29
  • My first thoughts were that I get all the graph nodes/edges which have constraints defined for them and check whether they match user's profile, if not the algorithm would return false and the isTraversable function would set that edge or node to 0 or false=non-traversable. All the traversable nodes/edges will be considered for the shortest path algorithm. If I exclude/prune the nodes or edges which are non-traversable at this time, in case of change in the route I won't be able to use them again in graph. That is, in a dynamic system. – NKK Dec 13 '13 at 18:30
  • Is that also what you said? Because I still need to do it in two steps. – NKK Dec 13 '13 at 18:30
  • Can't you just check the node's constraints as part of the shortest path traversal? Rather than setting some traversable flag on the node, just check the constraints as you go. You need to touch the node to get all outgoing edges, etc. so when you get to a node, check the constraints right off the bat. If the current user can't use the current node for whatever reason then you're done with it, simply back out and continue with the shortest-path. – Evicatos Dec 13 '13 at 18:43
  • That sounds good but I am not sure if it works for this project. Let me explain more: I have space cells (representing building objects such as doors, corridors, rooms, lifts, etc.) as graph nodes. These space cells either have constraint(s) associated with them or not. In case they don't, then they are always traversable. But if they do have constraints then the condition in which these constraints would apply should be checked... – NKK Dec 13 '13 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.