TheAlgorithms/Python · error · ValueError

No path from vertex: {self.source_vertex} to vertex: {target

Error message

No path from vertex: {self.source_vertex} to vertex: {target_vertex}

What it means

Raised by Graph.shortest_path (graphs/breadth_first_search_shortest_path.py:80) when the BFS parent map has no entry for target_vertex — meaning the target was never reached during breadth-first search from source_vertex. Typical causes: the target is not in the graph at all, or it lies in a different connected component (or is unreachable in a directed graph).

Source

Thrown at graphs/breadth_first_search_shortest_path.py:80

        Traceback (most recent call last):
            ...
        ValueError: No path from vertex: G to vertex: Foo

        Case 2 - The path is found.
        >>> g.shortest_path("D")
        'G->C->A->B->D'
        >>> g.shortest_path("G")
        'G'
        """
        if target_vertex == self.source_vertex:
            return self.source_vertex

        target_vertex_parent = self.parent.get(target_vertex)
        if target_vertex_parent is None:
            msg = (
                f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
            )
            raise ValueError(msg)

        return self.shortest_path(target_vertex_parent) + f"->{target_vertex}"


if __name__ == "__main__":
    g = Graph(graph, "G")
    g.breath_first_search()
    print(g.shortest_path("D"))
    print(g.shortest_path("G"))
    print(g.shortest_path("Foo"))

View on GitHub (pinned to f5988cc097)

Solutions

1. Call breath_first_search() once after constructing the Graph, before any shortest_path call
2. Verify the target exists and was reached: check target_vertex in g.parent (or in the graph) before calling shortest_path
3. For directed graphs, confirm the target is downstream of the source vertex

Example fix

# before
print(g.shortest_path("D"))  # may raise if D unreachable

# after
g.breath_first_search()
if "D" in g.parent or "D" == g.source_vertex:
    print(g.shortest_path("D"))
else:
    print("no path")

g.breath_first_search()  # must run first to populate g.parent
if target != g.source_vertex and target not in g.parent:
    raise LookupError(f"{target!r} is not reachable from {g.source_vertex!r}")
path = g.shortest_path(target)

try:
    print(g.shortest_path(target))
except ValueError:
    print(f"no path to {target}")

When it happens

Trigger: g.shortest_path("Foo") where "Foo" was never a vertex; g.shortest_path("D") where D belongs to a component disconnected from the BFS source; calling shortest_path before breath_first_search() was run so parent is empty.

Common situations: Looking up a path to a vertex that was never added; directed graphs where the target is only reachable in the reverse direction; forgetting to call breath_first_search() after constructing Graph(graph, source).

Related errors

• Algorithm is unable to find solution
• Negative cycle found
• Vertex indexes must be in [0; size).
• You need to set maximum flow algorithm before.
• You should execute algorithm before using its result!

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/9d25b39d61183928. Report an issue: GitHub.