¿El camino más corto en un gráfico no dirigido?

Entonces pensé que esta pregunta (aunque algo básica) pertenecía aquí:

Digamos que tengo un gráfico de tamaño 100 nodos dispuestos en un patrón de 10x10 (piense en el tablero de ajedrez). El gráfico no está dirigido y no está ponderado. Moverse por el gráfico implica mover tres espacios hacia adelante y un espacio hacia la derecha o hacia la izquierda (similar a cómo se mueve un caballero de ajedrez a través de un tablero).

Dado un nodo de inicio fijo, ¿cómo se puede encontrar el camino más corto a cualquier otro nodo en el tablero?

Imaginé que solo habría una ventaja entre los nodos que son movimientos viables. Entonces, dada esta información, me gustaría encontrar la ruta más corta desde un nodo inicial hasta un nodo final.

Mi pensamiento inicial fue que cada borde está ponderado con el peso 1. Sin embargo, el gráfico no está dirigido, por lo que Djikstras no sería un ajuste ideal. Por lo tanto, decidí hacerlo usando una forma alterada de una primera búsqueda en profundidad.

Sin embargo, por mi vida no pude visualizar cómo obtener el camino más corto usando la búsqueda.

Otra cosa que intenté fue poner el gráfico en forma de árbol con el nodo inicial como raíz, y luego seleccionar el resultado más superficial (número de fila más bajo) que me dio el nodo final deseado ... esto funcionó, pero fue increíblemente ineficiente, y por lo tanto no funcionaría para un gráfico más grande.

¿Alguien tiene alguna idea que pueda señalarme en la dirección correcta en este caso?

Muchas gracias.

(Intenté poner una visualización del gráfico, pero no pude debido a mi baja reputación)

Si los bordes en el gráfico solo representan movimientos válidos entre ciertas posiciones, usar Dijkstra funcionaría bien. Sin embargo, como el gráfico no está ponderado, sería excesivo. Una simple búsqueda de amplitud primero dará la respuesta óptima.

Nicholas ya proporcionó una respuesta perfecta. Sin embargo, permítame abordar su intento original de utilizar la búsqueda en profundidad.

Primero, ya sea Dijkstra (que funciona bien con nodos no ponderados como lo señaló Nicholas Mancuso) o la búsqueda de amplitud genera un desperdicio exponencial de su memoria. Sin embargo, su ventaja es que nunca vuelven a expandir ningún nodo mientras se les garantiza que encontrarán soluciones óptimas. Desafortunadamente, su limitación es bastante importante y no se debe esperar que se amplíe razonablemente.

$d_{max}$$k$$i$$d_{max} + i\times k$$d_{max}=k=1$ entonces tiene la garantía de encontrar la solución óptima mientras usa la memoria lineal en la profundidad de la solución.

$\frac{b}{b-1}$$b$

Salud,