Recorrido en anchura (BFS)

from collections import deque

grafo = {}


def arista(a, b):                                   # no dirigida: se apunta en los dos sentidos
    grafo.setdefault(a, []).append(b)
    grafo.setdefault(b, []).append(a)


for a, b in [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"), ("D", "F"), ("E", "F"), ("F", "G")]:
    arista(a, b)

dist = {"A": 0}
padre = {}
cola = deque(["A"])
orden = []
while cola:
    u = cola.popleft()
    orden.append(u)
    for v in grafo[u]:
        if v not in dist:                           # la primera vez que se ve: por el camino más corto
            dist[v] = dist[u] + 1
            padre[v] = u
            cola.append(v)

print("Orden de visita:", " ".join(orden))
for n in orden:
    print(f"  dist({n}) = {dist[n]}")

camino = []
n = "G"
while n is not None:                                # de G hacia atrás
    camino.insert(0, n)
    n = padre.get(n)
print("Camino más corto de A a G:", " → ".join(camino))

const grafo = new Map();

function arista(a, b) {                             // no dirigida: se apunta en los dos sentidos
    if (!grafo.has(a)) grafo.set(a, []);
    if (!grafo.has(b)) grafo.set(b, []);
    grafo.get(a).push(b);
    grafo.get(b).push(a);
}

for (const [a, b] of [["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"], ["C", "E"], ["D", "F"], ["E", "F"], ["F", "G"]]) arista(a, b);

const dist = new Map([["A", 0]]);
const padre = new Map();
const cola = ["A"];
const orden = [];
while (cola.length > 0) {
    const u = cola.shift();                         // shift() es O(n): con colas enormes, mejor un índice
    orden.push(u);
    for (const v of grafo.get(u)) {
        if (!dist.has(v)) {                         // la primera vez que se ve: por el camino más corto
            dist.set(v, dist.get(u) + 1);
            padre.set(v, u);
            cola.push(v);
        }
    }
}
console.log("Orden de visita: " + orden.join(" "));
for (const n of orden) console.log(`  dist(${n}) = ${dist.get(n)}`);

const camino = [];
for (let n = "G"; n !== undefined; n = padre.get(n)) camino.unshift(n);   // de G hacia atrás
console.log("Camino más corto de A a G: " + camino.join(" → "));

using System;
using System.Collections.Generic;

class Program {
    static readonly Dictionary<string, List<string>> grafo = new();

    static void Arista(string a, string b) {             // no dirigida: se apunta en los dos sentidos
        if (!grafo.ContainsKey(a)) grafo[a] = new List<string>();
        if (!grafo.ContainsKey(b)) grafo[b] = new List<string>();
        grafo[a].Add(b);
        grafo[b].Add(a);
    }

    static void Main() {
        foreach (var (a, b) in new[] { ("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"), ("D", "F"), ("E", "F"), ("F", "G") }) Arista(a, b);

        var dist = new Dictionary<string, int> { ["A"] = 0 };
        var padre = new Dictionary<string, string>();
        var cola = new Queue<string>();
        var orden = new List<string>();
        cola.Enqueue("A");
        while (cola.Count > 0) {
            string u = cola.Dequeue();
            orden.Add(u);
            foreach (string v in grafo[u]) {
                if (!dist.ContainsKey(v)) {                 // la primera vez que se ve: por el camino más corto
                    dist[v] = dist[u] + 1;
                    padre[v] = u;
                    cola.Enqueue(v);
                }
            }
        }
        Console.WriteLine("Orden de visita: " + string.Join(" ", orden));
        foreach (string n in orden) Console.WriteLine(
quot;  dist({n}) = {dist[n]}");

        var camino = new List<string>();
        for (string? n = "G"; n != null; n = padre.GetValueOrDefault(n)) camino.Insert(0, n);   // de G hacia atrás
        Console.WriteLine("Camino más corto de A a G: " + string.Join(" → ", camino));
    }
}

<?php
$grafo = [];
foreach ([["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"], ["C", "E"], ["D", "F"], ["E", "F"], ["F", "G"]] as [$a, $b]) {                    // no dirigida: se apunta en los dos sentidos
    $grafo[$a][] = $b;
    $grafo[$b][] = $a;
}

$dist = ["A" => 0];
$padre = [];
$cola = new SplQueue();
$cola->enqueue("A");
$orden = [];
while (!$cola->isEmpty()) {
    $u = $cola->dequeue();
    $orden[] = $u;
    foreach ($grafo[$u] as $v) {
        if (!isset($dist[$v])) {                   // la primera vez que se ve: por el camino más corto
            $dist[$v] = $dist[$u] + 1;
            $padre[$v] = $u;
            $cola->enqueue($v);
        }
    }
}
echo "Orden de visita: " . implode(" ", $orden) . "\n";
foreach ($orden as $n) echo "  dist($n) = {$dist[$n]}\n";

$camino = [];
for ($n = "G"; $n !== null; $n = $padre[$n] ?? null) array_unshift($camino, $n);   // de G hacia atrás
echo "Camino más corto de A a G: " . implode(" → ", $camino) . "\n";

from collections import deque

plano = [
    "S.#.......",
    ".##.####.#",
    "....#....#",
    ".##...##.E",
    "...#.#....",
]
filas, cols = len(plano), len(plano[0])
m = [list(fila) for fila in plano]
ini = fin = 0
for f in range(filas):
    for c in range(cols):
        if m[f][c] == "S":
            ini = f * cols + c                      # cada casilla es un nodo: f * cols + c
        if m[f][c] == "E":
            fin = f * cols + c
movimientos = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # arriba, abajo, izquierda, derecha
previa = [-2] * (filas * cols)                      # -2: sin descubrir
previa[ini] = -1
cola = deque([ini])
while cola:
    u = cola.popleft()
    if u == fin:
        break                                       # la primera vez que se llega es por el camino más corto
    for df, dc in movimientos:
        f, c = u // cols + df, u % cols + dc
        if 0 <= f < filas and 0 <= c < cols and m[f][c] != "#" and previa[f * cols + c] == -2:
            previa[f * cols + c] = u
            cola.append(f * cols + c)

if previa[fin] == -2:
    print("No hay salida")
else:
    pasos = 1
    p = previa[fin]
    while p != ini:                                 # de la salida hacia atrás
        m[p // cols][p % cols] = "*"
        pasos += 1
        p = previa[p]
    print(f"Camino más corto: {pasos} pasos")
    for fila in m:
        print("".join(fila))

const plano = [
    "S.#.......",
    ".##.####.#",
    "....#....#",
    ".##...##.E",
    "...#.#....",
];
const filas = plano.length, cols = plano[0].length;
const m = plano.map((fila) => [...fila]);
let ini = 0, fin = 0;
for (let f = 0; f < filas; f++)
    for (let c = 0; c < cols; c++) {
        if (m[f][c] === "S") ini = f * cols + c;    // cada casilla es un nodo: f * cols + c
        if (m[f][c] === "E") fin = f * cols + c;
    }
const df = [-1, 1, 0, 0], dc = [0, 0, -1, 1];     // arriba, abajo, izquierda, derecha
const previa = new Array(filas * cols).fill(-2);   // -2: sin descubrir
previa[ini] = -1;
const cola = [ini];
for (let i = 0; i < cola.length; i++) {           // un índice que avanza en vez de shift()
    const u = cola[i];
    if (u === fin) break;                         // la primera vez que se llega es por el camino más corto
    for (let k = 0; k < 4; k++) {
        const f = Math.floor(u / cols) + df[k], c = (u % cols) + dc[k];
        if (f < 0 || f >= filas || c < 0 || c >= cols || m[f][c] === "#" || previa[f * cols + c] !== -2) continue;
        previa[f * cols + c] = u;
        cola.push(f * cols + c);
    }
}
if (previa[fin] === -2) console.log("No hay salida");
else {
    let pasos = 1;
    for (let p = previa[fin]; p !== ini; p = previa[p]) {   // de la salida hacia atrás
        m[Math.floor(p / cols)][p % cols] = "*";
        pasos++;
    }
    console.log(`Camino más corto: ${pasos} pasos`);
    for (const fila of m) console.log(fila.join(""));
}

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        string[] plano = {
        "S.#.......",
        ".##.####.#",
        "....#....#",
        ".##...##.E",
        "...#.#....",
        };
        int filas = plano.Length, cols = plano[0].Length;
        var m = new char[filas][];
        int ini = 0, fin = 0;
        for (int f = 0; f < filas; f++) {
            m[f] = plano[f].ToCharArray();
            for (int c = 0; c < cols; c++) {
                if (m[f][c] == 'S') ini = f * cols + c;     // cada casilla es un nodo: f * cols + c
                if (m[f][c] == 'E') fin = f * cols + c;
            }
        }
        int[] df = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };  // arriba, abajo, izquierda, derecha
        var previa = new int[filas * cols];
        Array.Fill(previa, -2);                             // -2: sin descubrir
        previa[ini] = -1;
        var cola = new Queue<int>();
        cola.Enqueue(ini);
        while (cola.Count > 0) {
            int u = cola.Dequeue();
            if (u == fin) break;                            // la primera vez que se llega es por el camino más corto
            for (int k = 0; k < 4; k++) {
                int f = u / cols + df[k], c = u % cols + dc[k];
                if (f < 0 || f >= filas || c < 0 || c >= cols || m[f][c] == '#' || previa[f * cols + c] != -2) continue;
                previa[f * cols + c] = u;
                cola.Enqueue(f * cols + c);
            }
        }
        if (previa[fin] == -2) {
            Console.WriteLine("No hay salida");
            return;
        }
        int pasos = 1;
        for (int p = previa[fin]; p != ini; p = previa[p]) {  // de la salida hacia atrás
            m[p / cols][p % cols] = '*';
            pasos++;
        }
        Console.WriteLine(
quot;Camino más corto: {pasos} pasos");
        foreach (var fila in m) Console.WriteLine(new string(fila));
    }
}

<?php
$plano = [
    "S.#.......",
    ".##.####.#",
    "....#....#",
    ".##...##.E",
    "...#.#....",
];
$filas = count($plano);
$cols = strlen($plano[0]);
$m = $plano;                                       // en PHP se puede cambiar un carácter de un string: $s[3] = "*"
$ini = $fin = 0;
for ($f = 0; $f < $filas; $f++)
    for ($c = 0; $c < $cols; $c++) {
        if ($m[$f][$c] === "S") $ini = $f * $cols + $c;   // cada casilla es un nodo: f * cols + c
        if ($m[$f][$c] === "E") $fin = $f * $cols + $c;
    }
$movimientos = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // arriba, abajo, izquierda, derecha
$previa = array_fill(0, $filas * $cols, -2);       // -2: sin descubrir
$previa[$ini] = -1;
$cola = new SplQueue();
$cola->enqueue($ini);
while (!$cola->isEmpty()) {
    $u = $cola->dequeue();
    if ($u === $fin) break;                        // la primera vez que se llega es por el camino más corto
    foreach ($movimientos as [$df, $dc]) {
        $f = intdiv($u, $cols) + $df;
        $c = $u % $cols + $dc;
        if ($f < 0 || $f >= $filas || $c < 0 || $c >= $cols || $m[$f][$c] === "#" || $previa[$f * $cols + $c] !== -2) continue;
        $previa[$f * $cols + $c] = $u;
        $cola->enqueue($f * $cols + $c);
    }
}
if ($previa[$fin] === -2) {
    echo "No hay salida\n";
} else {
    $pasos = 1;
    for ($p = $previa[$fin]; $p !== $ini; $p = $previa[$p]) {   // de la salida hacia atrás
        $m[intdiv($p, $cols)][$p % $cols] = "*";
        $pasos++;
    }
    echo "Camino más corto: $pasos pasos\n";
    foreach ($m as $fila) echo $fila, "\n";
}