Skip to content

Implement furthest nodes with shortest path #108

@sraaphorst

Description

@sraaphorst

In general, longest path is an NP-hard problem (except for trees, which our perfect graphs are).

However, we don't exactly want longest path: what we want is to find the maximum length shortest path, which can be done via a BFS at each node, keeping track of the pair of cells that are the furthest apart. Ultimately, these can be used for the start and the goal position to presumably make the maze more challenging.

This should be calculable in time O(w2h2) simply by starting at each cell, of which there are at most w * h, and running a BFS, which will take at most w * h steps.

By implementing BFS for each maze type, we will be able to do this easily, as well as find the connected components easily, and possibly have enough information to generalize solutions to AbstractMaze.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestsharedCode common to all libraries

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions