I’m not sure whether I’m using the correct terminology here. I’m trying to come up with an algorithm that let’s me find a vertex in an arbitrary graph so that the vertex has minimum distance to the farthest vertices.
And additionally, I’m also trying to come up with an algorithm that let’s me find 2 vertices instead of one, again minimizing the distance from the farthest vertices to either one of these two vertices.
My intuition says that I should come up with an algorithm that calculates the shortest paths between all vertices in the graph, and look at the paths, and find the vertices with the highest traffic. But I have trouble coming up with a concrete algorithm since I have no prior experience with this at all. I tried to google this problem, unsuccessfully. Any guidance would be greatly appreciated.
You need to really assess what you are trying to model in your algorithm.
What are the inputs to the algorithm and what are the possible outputs. I suggest you start by reading into the mathematics of Graphs.
In a graph, a ‘farthest’ vertex is a very subjective term and it really depends on a certain chosen 0,0 or the ‘index’ or ‘current’ vertex.
Start by learning basics of graphs here (Just find and click any of the lecture notes titled ‘graphs’)
(The above theory is of course just my opinion and you can choose to learn about graphs from anywhere)
The most important algorithms for ‘finding shortest paths’ are:
- Dijkstra’s algorithm solves the single-source shortest path problem.
- Bellman–Ford algorithm solves the single-source problem if edge
weights may be negative. - A* search algorithm solves for single pair shortest path using
heuristics to try to speed up the search. - Floyd–Warshall algorithm solves all pairs shortest paths.
- Johnson’s algorithm solves all pairs shortest paths, and may be
faster than Floyd–Warshall on sparse graphs. - Viterbi algorithm solves the shortest stochastic path problem with an
additional probabilistic weight on each node.
A more comprehensive study can be found on the Wikipedia page
1
After a bit of reading here is what I came up with:
To minimize the distance to the farthest vertices, we have to find the farthest vertices first. So the first step is to generate an algorithm that finds the shortest path between two vertices.
We then run that algorithm through all vertices and only record the longest of those shortest paths.
The algorithm to find the shortest path for an undirected, weighted graph, which is what I have in my problem, is Dijkstra’s algorithm, but we only record the distance for the two vertices that are farthest away. To visualize this, for any vertex v in a graph G=(V, E), where V={v1..vn}, we record distancev = max{distance(v, v1), distance(v, v2)…distance(v, vn)}, where distance is defined as the shortest distance between two vertices.
Once we gather all the distances to the farthest vertices, we sort the results to find the minimum. That will be the answer.