Kürzester Weg in einem ungerichteten Graphen?

Also dachte ich, dass diese (wenn auch etwas grundlegende) Frage hierher gehört:

Angenommen, ich habe ein Diagramm mit einer Größe von 100 Knoten, die in einem 10x10-Muster angeordnet sind (siehe Schachbrett). Das Diagramm ist ungerichtet und ungewichtet. Um sich durch die Grafik zu bewegen, müssen Sie drei Felder nach vorne und ein Feld nach rechts oder links bewegen (ähnlich wie sich ein Schachritter über ein Brett bewegt).

Wie würde man bei einem festen Anfangsknoten den kürzesten Weg zu einem anderen Knoten auf der Platine finden?

Ich stellte mir vor, dass es nur eine Kante zwischen Knoten geben würde, die brauchbare Bewegungen sind. Angesichts dieser Informationen möchte ich den kürzesten Weg von einem Startknoten zu einem Endknoten finden.

Mein erster Gedanke war, dass jede Kante mit dem Gewicht 1 gewichtet wird. Die Grafik ist jedoch ungerichtet, sodass Djikstras nicht ideal passen würden. Aus diesem Grund habe ich mich dazu entschlossen, eine geänderte Form einer Tiefensuche zu verwenden.

Ich konnte mir jedoch nicht vorstellen, wie ich mit der Suche den kürzesten Weg finden kann.

Eine andere Sache, die ich versuchte, war, den Graphen in Baumform mit dem Startknoten als Wurzel zu platzieren und dann das flachste (niedrigste Zeilennummer) Ergebnis auszuwählen, das mir den gewünschten Endknoten gab ... dies funktionierte, war aber unglaublich ineffizient und daher würde für eine größere Grafik nicht funktionieren.

Hat jemand irgendwelche Ideen, die mir in dieser Hinsicht in die richtige Richtung weisen könnten?

Vielen Dank.

(Ich habe versucht, eine Visualisierung des Diagramms zu erstellen, konnte dies jedoch aufgrund meines schlechten Rufs nicht.)

Wenn die Kanten in der Grafik nur gültige Bewegungen zwischen bestimmten Positionen darstellen, funktioniert die Verwendung von Dijkstra problemlos. Da das Diagramm jedoch ungewichtet ist, wäre es zu viel des Guten. Eine einfache Breitensuche liefert die optimale Antwort.

Nicholas gab bereits eine perfekte Antwort. Lassen Sie mich jedoch auf Ihren ursprünglichen Versuch eingehen, die Tiefensuche zu verwenden.

Erstens, entweder Dijkstra (was bei ungewichteten Knoten, wie von Nicholas Mancuso bemerkt, gut funktioniert) oder die Breitensuche verursachen eine exponentielle Verschwendung Ihres Speichers. Ihr Vorteil ist jedoch, dass sie keine Knoten erneut erweitern, während sie garantiert optimale Lösungen finden. Leider ist ihre Einschränkung sehr wichtig und es sollte nicht erwartet werden, dass sie angemessen skaliert werden.

$d_{max}$$k$$i$$d_{max} + i\times k$$d_{max}=k=1$ Dann finden Sie garantiert die optimale Lösung, während Sie den linearen Speicher in der Tiefe der Lösung verwenden.

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

Prost,