まずは「XからYへの単純パスを1つ求めてください」という問題を考えます。これは例えば次のようなDFSにより求めることができます。

（※元の問題はマルチテストケースなので、exit()するのではなく適切にdfsメソッド内から脱出する必要があります）

# 訪問済み頂点のset
visited_vertex_set = set()
# Xから今の頂点に至るまでのpath
path_list = list()

def dfs(current_vertex):
    path_list.append(current_vertex)
    visited_vertex_set.add(next_vertex)
    # Yにたどり着いたら終了
    if current_vertex == Y:
        output(path_list)
        exit()
    # まだ行ったことのない隣の頂点へ移動
    for next_vertex in neighborhood(current_vertex):
        if next_vertex not in visited_vertex_set:
            dfs(next_vertex)
    # どうやってもYにたどり着かなかったら前の頂点へ戻る
    path_list.pop()

dfs(X)

一般に辞書順最小のものを得るには、先頭から順に選べる最小のものを貪欲に選ぶのが最適です。よって、隣の頂点へ移動するときの頂点順を番号の小さい順にするように、上のコードに1行変更を加えることで辞書順最小の解を得ることができます。

# 訪問済み頂点のset
visited_vertex_set = set()
# Xから今の頂点に至るまでのpath
path_list = list()

def dfs(current_vertex):
    path_list.append(current_vertex)
    visited_vertex_set.add(next_vertex)
    # Yにたどり着いたら終了
    if current_vertex == Y:
        output(path_list)
        exit()
    # まだ行ったことのない隣の頂点へ移動
    for next_vertex in sorted(neighborhood(current_vertex)):  # <---- ここだけ変更
        if next_vertex not in visited_vertex_set:
            dfs(next_vertex)
    # どうやってもYにたどり着かなかったら前の頂点へ戻る
    path_list.pop()

dfs(X)