0

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.

  • @RobertHarvey Thanks but could you please explain how is that helping me with what I asked? I don't care for the running time. At this time I would like to make an algorithm that works these steps, after I've done that part, I will try to optimize it. – NKK Jan 8 '14 at 18:42
  • 1
    You asked for examples of data structures and algorithms that would help you with a shortest path algorithm. The link provides that. Selecting the correct data structure is not premature optimization; it is an essential part of the process. – Robert Harvey Jan 8 '14 at 18:43
  • I know Dijkstra algorithm but my problem isn't the shortest path right now, I want to implement the procedure above first and I don't know how to write the algorithm/pseudo- algorithm for it. – NKK Jan 8 '14 at 18:48
  • 2
    What procedure? If you're not interested in applying an algorithm in specific, any old graph data structure will do. The traversal algorithms are obvious. I really think you ought to take a few minutes and study the slides I linked. The selection of a proper data structure is the first step, not an afterthought. – Robert Harvey Jan 8 '14 at 18:51
2

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.

  • In your scenario, the pathfinder (agreed on A*) would have to have a special case for the specific high weight to cover the scenario where no traversable path exists but the graph is still connected. – Steven Evers Jan 8 '14 at 20:44
  • I didn't explain the whole problem, maybe it clears why I have to check first if a node is traversable or not. The problem is that the users who enter the navigation system have different capability, for example if the user of the system can't walk the navigation system should exclude the paths with stair nodes in them. Similarly, if in order to enter a room the user needs to have a key or be an staff member, the function (the one I explained above) checks for each neighbor node (the children of the current node) and see whether for a given user on these nodes the conditions holds true – NKK Jan 9 '14 at 9:49
  • If the condition holds true, the function returns isTraversable and that node will be considered for the final path calculation. I can also use Dijkstra at same time for the neighbor nodes and set the edge cost for them. The cost will be a combination of Monetary,Time and energy cost. But since these are user preferences they come later on. First it's important to find whether a node is traversable at all. I hope this explains more. – NKK Jan 9 '14 at 9:54
  • It doesn't matter why it's not traversable. Trust me, if you give non-traversable edges an infinite cost, Dijkstra's algorithm not only works, but has significant advantages. Or just remove the edge outright in the step where you loop through the neighbors. You seem to be having difficulty wrapping your head around that, so just try it and see for yourself. – Karl Bielefeldt Jan 9 '14 at 13:42
  • @KarlBielefeldt That is true, I am not expert in writing algorithms and have difficulties making a modification. I had to edit my question so maybe now it's more clear. My problem isn't pruning the graph or set a high cost value on the edges, I want to know how can I modify Dijkstra to fit my purpose. – NKK Jan 9 '14 at 14:27
0

With all due respect, I find most answers and comments so far kind of confusing, and there is no straight answer yet. For instance there is no point speaking of heuristics (thus of A* algorithm) since we do not have any information to help guide the search, and besides the issue as clearly stated is not search or performance, but the matter of node traversability.

Also, the trick of setting a high cost for non-traversable nodes works to some extent but... The problem is that those nodes will still remain in the graph, and will be searched like any other, which will affect performance later on. The other issue is that a high node cost won't help if there is no other solution path; in such case a path might be found that goes through a non-traversable node (which would clearly be a major "bug" with the program!) So for both reasons it is a must to remove non-traversable nodes.

Now, given the problem as stated, and since the author knows Dijkstra algorithm (which is the most appropriate for the given scenario anyway), it is simply a matter of modifying the part of the algorithm that generates the children of a node and inserts them into the queue. That is, instead of enqueuing them all, unconditionally, we can use the user-specific isTraversable function to determine which to enqueue and which to discard.

Below is some pseudocode (largely adapted from cprogramming.com), with the additional test you need in uppercase:

/* Given graph G, with edges E of the form (v1, v2) and vertices V, and a source vertex s
* 
*  dist : array of distances from the source to each vertex
*  prev : array of pointers to preceding vertices
*  i    : loop index
*  U    : list or heap of vertices
*/

/* Initialization: set every distance to INFINITY until we discover a path */
for i = 0 to |V| - 1
    dist[i] = INFINITY
    prev[i] = NULL
dist[s] = 0    /* The distance from the source to itself is zero */

/* Examine the many alternative paths, always picking "the vertex, v, with the
 * shortest path to s" first, to guarantee finding the optimal solution */

while (U is not empty)
   pick the vertex, u, in U with the shortest path to s
   if u is the goal
        return u
   if dist[u] is INFINITY
       return error: no solution
   remove u from U
   for each child node v of u  /* edge (u, v) */
        if v is in U
            IF v IS_TRAVERSABLE
                if(dist[u] + length(u, v) < dist[v])
                    dist[v] = dist[u] + length(u, v)
                    prev[v] = u
            ELSE
                remove v from u

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.