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$– John L.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.
answered Dec 7, 2018 at 13:02
$\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\}$.
answered Dec 7, 2018 at 14:11