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 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\}$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.