Implementing Dijkstra with Predecessors

The function accepts a dictionary mapping each string vertex label to a dictionary of neighbour labels and non-negative integer edge weights. Every referenced vertex must exist as a key, including vertices with no outgoing edges. Directed edges need not have a reverse edge. A zero-weight edge is valid; a negative or Boolean weight violates this teaching contract.

Set the start distance to zero and all others to infinity. Keep an unvisited set and a predecessor dictionary. At each step choose the unvisited vertex with the smallest tentative distance; the secondary string-label key gives a deterministic alphabetical tie rule. If the smallest distance is infinite, the remaining vertices are unreachable from the start and the search can stop.

For an unsettled neighbour, compare distance[current]+edge_weight with the neighbour’s previous distance. A strict improvement replaces both distance and predecessor. The choice uses the cumulative route cost from the original start, not merely the smallest outgoing edge of the latest vertex. The non-negative-weight assumption supports the claim that a selected minimum can be settled.

In the fixture, P first offers Q cost 6 and R cost 2. Selecting R improves Q to 3 and offers T cost 10. Selecting Q improves T to 6. The predecessor chain is T←Q←R←P. Vertices settled on another branch are not automatically part of the chosen route; only predecessor links reconstruct that route.

When the target has a finite distance, start from it and follow predecessors to the start, then reverse the list. If start equals target, the valid result is cost zero and a one-vertex route. If no route exists, the function returns (None,[]). Distinguish that explicit failure result from a valid zero-cost path.

The simple set-min implementation takes O(V²+E) work in the usual adjacency-dictionary model because repeated minimum selection scans remaining vertices. A suitable priority queue can improve selection on sparse graphs, but adds implementation details and stale-entry handling. Test the written version against an independent all-pairs algorithm on small graphs, and verify that every returned step is a real directed edge whose costs sum to the reported distance.

def dijkstra(graph, start, target):
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError('Use string vertex labels')
    if start not in graph or target not in graph:
        raise ValueError('Start and target must exist')
    for neighbours in graph.values():
        for vertex, weight in neighbours.items():
            if vertex not in graph or type(weight) is not int or weight < 0:
                raise ValueError('Use known vertices and non-negative integer weights')
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0
    previous = {}
    unvisited = set(graph)
    while unvisited:
        current = min(unvisited, key=lambda vertex: (distance[vertex], vertex))
        if distance[current] == float('inf'):
            break
        unvisited.remove(current)
        if current == target:
            break
        for neighbour, weight in graph[current].items():
            if neighbour in unvisited:
                candidate = distance[current] + weight
                if candidate < distance[neighbour]:
                    distance[neighbour] = candidate
                    previous[neighbour] = current
    if distance[target] == float('inf'):
        return None, []
    path = [target]
    while path[-1] != start:
        path.append(previous[path[-1]])
    return distance[target], path[::-1]

graph = {'P': {'Q': 6, 'R': 2}, 'Q': {'T': 3}, 'R': {'Q': 1, 'T': 8}, 'T': {}}
print(dijkstra(graph, 'P', 'T'))
print(dijkstra(graph, 'T', 'P'))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.