I am developing a game and this is the task I was given: The road map of a remote island in the country is given. At island there are N villages (numbered from 1 to N) that are connected connected to each other by M roads, each of which is a double road. two-way roads connecting two villages. Consider a given that it is possible to travel from any village on the island to any other, by means of the roads in the road network. To date there is no public library on the island. Ideally, every village should have its own. But the public money is not enough. is enough for only one public library, which should be necessarily be placed in one of the island's villages. We call the "distance" of a village from the library the minimum the minimum number of roads we have to travel to get from village to it (i.e., the number of edges in the shortest possible distance from the village to the library). path). For example, if the library is located in village 1, then village 1 is at a distance of 0 from the library. If village 2 is adjacent to 1 (i.e. directly connected to it by a road), then village 2 is at a distance of 1 from the library (i.e. it is directly connected to the library), then village 2 is at a distance of 1 from the library. library. If village 3 is a neighbour of 2 but not a neighbour of 1 (i.e. directly connected to village 2 but not to the village 1), then village 3 is at distance 2 from the library. And and so on. We want to place the library such that the distance of farthest village from it is the smallest possible distance.
What i have to do is find the distance of the village furthest away of the most effective library location
I know it can be solved with a BFS algorithm but there must be a more effective algorithm