Collaborative graph exploration algorithm

Given an undirected graph G of (10 .. 500) vertices and (vertice_count .. 1000) edges.
A vertex can have (1 .. 6) edges. All edges have a unique cost of 1.

Given K agents, all starting from the same vertex START.

What would be the best way to explore the graph to visit all the vertices in as little time as possible?

I tried running a DFS from START which gives me all the shortest paths to the “leaves” of the graph and then sort the paths by their length.

Unfortunately there are often more paths than there are agents, so I have to re-assign agents which have explored the shortest paths. That’s where I’m stuck and would appreciate any kind of help (suggestions, ideas, algorithms…)

Go to Source
Author: ZogStriP