# Shortest path common core(s) question

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.