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