# Shortest distance from multiple points to one point

I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $$v_1,v_2,\dots,v_r$$ be the nodes on a graph with distance $$d_1,d_2,\dots,d_r$$ to the end node $$v$$. I want the shortest $$d$$ to $$v$$.

• By (the usual) default, a graph means undirected graph. Can you clarify that in the question? – Apass.Jack Dec 7 '18 at 18:42

This is quite straightforward

• Reverse the direction of each edge.
• Apply single source shortest path algorithm with destination as the source.
• Reverse the direction again. (Optional, only if you want to preserve the originality of graph)

Time Complexity- With graph given as adjacency list, it takes $$O(E+V)$$ to reverse the directions of each edge. With graph given as adjacency matrix, it takes $$\theta(V^2)$$. Rest you can apply any single source shortest path algorithm like Dijkshtra.

Note that a graph with reverse edges of original one typically called as transpose of the original graph.

Add a new vertex $$s$$ to your graph and give it an edge to each of $$v_1, \dots, v_r$$. Then use your favourite shortest path algorithm to compute the shortest path from $$s$$ to $$v$$. That path has length $$1+\min\{d_1, \dots, d_r\}$$.