What graph traversal algorithm should I use?

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.

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.

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

Filed under: softwareengineering - @ 15:15

Thẻ: algorithms, graph, graph-traversal, java, pseudocode

What graph traversal algorithm should I use?

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.

You might also consider A* if your weights are distances. It’s more efficient in eliminating nodes you don’t need.

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

Filed under: softwareengineering - @ 15:15

Thẻ: algorithms, graph, graph-traversal, java, pseudocode

Thiết kế website giá rẻ

Danh mục

What graph traversal algorithm should I use?

What graph traversal algorithm should I use?