In Catan you can calculate the longest road by finding the longest (most roads) path which does not repeat any edges/roads, and does not cross through a vertex controlled by another player.
I started doing an algorithm that:
- sorts the roads into connected networks (note there is only one of these above)
- for each road/edge
- for each of the two verticies
- recurses if possible with all possible options
This depth first approach is falling over when the board starts to look like this! Any ideas how to do this more efficiently? I was looking at something like Dijkstra's algorithm, but that doesn't work.
