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$.
$\begingroup$ $\endgroup$
1 
- $\begingroup$ By (the usual) default, a graph means undirected graph. Can you clarify that in the question? $\endgroup$喜欢算法和数学– 喜欢算法和数学2018-12-07 18:42:53 +00:00Commented Dec 7, 2018 at 18:42
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
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.
$\begingroup$ $\endgroup$
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\}$.