Quale algoritmo di attraversamento grafico dovrei usare?

Il solito modo di risolvere quello sarebbe invece di fare un passo di pre-elaborazione prima di eseguire Dijkstra, basta eseguire Dijkstra e dare a tutti i bordi non traversabili un peso davvero elevato. In questo modo eviti di preelaborare nodi che non sono assolutamente nel percorso più breve e inoltre eviti il problema di non trovare un percorso che potrebbe essere effettivamente più breve, ma che viene dopo quando cerchi l'ordine dei bambini.

Potresti anche considerare A * se i tuoi pesi sono distanze. È più efficiente nell'eliminare i nodi che non ti servono.

Con tutto il dovuto rispetto, trovo la maggior parte delle risposte e dei commenti fino ad ora un po 'di confusione, e non c'è ancora una risposta diretta. Per esempio non ha senso parlare di euristica (quindi di algoritmo A *) dato che noi non abbiamo alcuna informazione che aiuti a guidare la ricerca, e inoltre il problema, come affermato chiaramente, è non ricerca o prestazioni, ma la questione del nodo traversabilità

Inoltre, il trucco di impostare un costo elevato per i nodi non interscambiabili funziona in una certa misura, ma ... Il problema è che quei nodi rimarranno ancora nel grafico e saranno ricercati come qualsiasi altro, il che influenzerà le prestazioni più tardi. L'altro problema è che il costo di un nodo alto non sarà di aiuto se non esiste un altro percorso di soluzione; in tal caso si può trovare un percorso che attraversa un nodo non traversabile (che sarebbe chiaramente un "bug" importante con il programma!) Quindi per entrambi i motivi è necessario rimuovere nodi non traversabili.

Ora, dato il problema come detto, e poiché l'autore conosce l'algoritmo Dijkstra (che è comunque il più appropriato per lo scenario dato), si tratta semplicemente di modificare la parte dell'algoritmo che genera i figli di un nodo e li inserisce nella coda. Cioè, invece di accodarli tutti, incondizionatamente, possiamo usare la funzione isTraversable specifica per utente per determinare quale accodare e quale scartare.

Di seguito alcuni pseudocodici (ampiamente adattati da cprogramming.com ), con il test aggiuntivo di cui hai bisogno in maiuscolo:

/* 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