Re: [graph] which algorithm/visitor to use?

From: hermann_at_[hidden]
Date: 2025-05-13 12:18:21

On 2025-05-13 13:10, Andrzej Krzemienski via Boost wrote:
>> 
> 
> Thanks. This is an important observation that although I am using
> something that can be modeled as a graph, using Boost.Graph may be a 
> bad
> choice.
> 
No, it is not, you only need a matching graph algorithm.

The distance is 1 for each edge if I understand the problem correctly.

For each flight you create an edge, so you need a graph allowing for 
multiple edges (to model flights between A and B of eg. different 
companies).

Use edge weight 1 for every edge and Dijkstra algorithm:
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
"It can be used to find the shortest path to a specific destination 
node, by terminating the algorithm after determining the shortest path 
to the destination node."

You can let the algorithm continue until the maximal number of edges 
plus 1 is reached at any vertex (works because a priority queue is 
used).

Boost allows for
https://www.boost.org/doc/libs/latest/libs/graph/doc/dijkstra_visitor.html

and
https://www.boost.org/doc/libs/latest/libs/graph/doc/dijkstra_shortest_paths.html

Regards,

Hermann.