Optimize distances between vertices in graph theory

Question

So imagine that I have a weighted graph with some random values ranging between $1$ and $20$, where this integer represents the amount of time required to travel to the node/vertex.

I wanted to know, through graph theory, if there is an algorithm that I can use to find the optimum location, where I can add another node/vertex, such that all or most vertices are reachable within 10 minutes.

I am new to graph theory so if this is a really simple question I am sorry. Thanks for helping.

Answer 1

A very simple (and definitely not optimal) algorithm would be the following.

1. Sort a list of your nodes in order of decreasing degree (intuitively, better connected nodes have a higher chance of being an optimum location).
2. First for the most connected node $a$: use Dijkstra's algorithm to find the shortest path between each one of the other nodes.
   1. As soon as you find a node $b$ such that the weighted distance (the sum of the weights of the edges in the path) from $a$ to $b$ is larger than 10, start over at the next-most connected node.
   2. If all the other nodes have a weighted distance $<10$, terminate the algorithm and return the node.

This is a quick and dirty algorithm, but might get the job done if your graphs are not too large. Since Dijkstra's algorithm is $\mathcal{O}(n^2)$ where $n$ is the number of nodes, this algorithm runs in worst case $\mathcal{O}(n^3)$.