Ho un problema con il calcolo dei percorsi più brevi su un grafico non pesato e non orientato.
Quale algoritmo utilizzo per calcolare il percorso più breve tra un nodo A e il nodo B che passa attraverso un nodo C su un grafo non orientato e non ponderato?
Puoi dividere la soluzione in 2 passaggi, trovare prima un percorso da A a C, quindi trovare uno da C a B e concatenarli.
Per trovare i singoli percorsi ti consigliamo di usare Dijkstra (dato che probabilmente non è previsto che non ci sia euristica per ottenere A *).
Come sottolineato da Cracket, dovrai dividere la soluzione per trovare un percorso da A a C e poi da C a B.
Tuttavia, Dijkstra non è necessario poiché il grafico non ha alcun peso. È sufficiente una semplice Breadth First Search (BFS), leggermente più semplice da implementare.
Inoltre, se dovessi implementare A *, nessun peso non significa che non puoi trovare un'euristica. Potresti comunque preferire i percorsi che attraversano i nodi con una certa proprietà come euristica.
Leggi altre domande sui tag graph