Word Ladder Problem with mandatory words in the middle

This can be done in exactly the same time complexity as Dijkstra's algorithm using a small augmentation. We replace every vertex v in the original graph with two vertices (v, 0) and (v, 1), denoting whether we've visited a detour yet or not. We're now searching for the shortest path from (start, x) to (end, 1), where x is 1 or 0 if start is or is not a detour, respectively.

The priority queue Q is initialized with only (start, x) at a priority/distance of 0. The main loop over neighbors in Dijkstra's algorithm transforms into this (pseudocode):

while Q is not empty:
    (v, has_detour) <- extract_min_heap(Q)

    for neighbor, edge_cost in neighbors[v]:
        detour_status <- has_detour | is_detour(neighbor)
        alt_cost = dist[v, has_detour] + edge_cost

        if alt_cost < dist[neigh, detour_status]:
            dist[neigh, detour_status] = alt_cost
            predecessor[neigh, detour_status] = (v, has_detour)
            add (neigh, detour_status) to Q with priority == alt_cost

Note that we don't construct the augmented graph G* explicitly through the original edge set, only implicitly through the auxiliary data structure of Dijkstra's. Of course, you could actually store the new graph, which is defined like so:

Given a directed graph G = (V, E),
Define a new directed graph G* = (V*, E*):

Vertex set V* := V x {0,1}

Edge set E* := {((v,1), (w,1)) | (v,w) ∈ E} 
             ∪ {((v,0), (w,0)) | (v,w) ∈ E and w ∉ detours} 
             ∪ {((v,0), (w,1)) | (v,w) ∈ E and w ∈ detours}

Since our new graph (on which we actually run Dijkstra's) has 2|V| vertices and 2|E| edges, the new asymptotic runtime and space complexity is the same as it was in the original implementation of Dijkstra's. Make sure to use a set or hashmap-based data structure for implementing is_detour() in O(1).

For a full Python implementation, see below. The code changes related to detours are almost all in that main loop: the majority of the code is building the standard word ladder graph. Building the graph can take |V|^2 * word_len or |V|*(word_len^2) + |E|, depending on how you do it. I chose the second approach, here.

def word_ladder(words: List[str],
                start_word_idx: int,
                end_word_idx: int,
                detour_idxs: List[int]) -> Optional[List[int]]:
    """Given a list of distinct equal length lowercase words,
      find a word ladder of minimum pairwise alphabetic distance
      from start to end if one exists, or return None otherwise"""

    def letter_dist(letter1: str, letter2: str) -> int:
        return abs(ord(letter1) - ord(letter2))

    detour_idx_set = set(detour_idxs)
    word_bases = collections.defaultdict(list)

    graph = collections.defaultdict(list)

    word_len = len(words[0])

    for i, word in enumerate(words):
        as_list = list(word)
        for j in range(word_len):
            old = as_list[j]
            as_list[j] = '0'
            word_base = ''.join(as_list)
            for other_word_idx in word_bases[word_base]:
                dist = letter_dist(old, words[other_word_idx][j])
                graph[i].append((other_word_idx, dist))
                graph[other_word_idx].append((i, dist))
            word_bases[word_base].append(i)
            as_list[j] = old

    distances = collections.defaultdict(lambda: math.inf)
    queue = []

    start_is_detour = 1 if start_word_idx in detour_idx_set else 0

    queue.append((0, start_word_idx, start_is_detour))
    distances[start_word_idx, start_is_detour] = 0

    parent = {}

    def reconstruct_ladder() -> List[int]:
        vert, detour_status = end_word_idx, 1
        path = []
        while (vert, detour_status) in parent:
            path.append(vert)
            vert, detour_status = parent[vert, detour_status]
        path.append(vert)
        path.reverse()
        return path

    while len(queue) != 0:
        distance, index, has_detour = heapq.heappop(queue)
        if distances[index, has_detour] != distance:
            continue

        for neighbor_idx, edge_cost in graph[index]:
            detour_status = has_detour | (neighbor_idx in detour_idx_set)

            if distance + edge_cost < distances[neighbor_idx, detour_status]:
                distances[neighbor_idx, detour_status] = distance + edge_cost
                parent[neighbor_idx, detour_status] = (index, has_detour)
                heapq.heappush(queue,
                               (distances[neighbor_idx, detour_status],
                                neighbor_idx, detour_status))

    if (end_word_idx, 1) not in parent:
        return None
    return reconstruct_ladder()

which, on your input, can be used like:

words = ['aaa', 'bbb', 'bab', 'aaf', 'aaz', 'baz', 'caa', 'cac', 'dac', 'dad', 'ead', 'eae', 'bae', 'abf', 'bbf']
start = 0
end = 1
detours = [12]

print(word_ladder(words=words, start_word_idx=start,
                  end_word_idx=end, detour_idxs=detours))

[0, 6, 7, 8, 9, 10, 11, 12, 2, 1]

Note that this implementation of Dijkstra doesn't use Decrease-Key, so the theoretical runtime is suboptimal. Of course, that's also true of most practical implementations; feel free to use a Fibonacci-Heap or similar if that's a concern.