0
$\begingroup$

Finding the shortest path from a source vertex to all other vertices in a graph!

I have sketched a proof of the correctness of Dijkstra's algorithm, using induction. Now I am looking to prove the "similar to Dijkstra's algorithm- the backwards algorithm"! It works by looking at the distance to the vertex closest from a source vertex, then the distance from those vertices ,.. and so on, until the shortest distance for all vertices has been found. My question is what is this algorithm called apart from "the backward algorithm". The only hint I have is that the Dijkstra's algorithm is called the forward algorithm.

$\endgroup$
  • $\begingroup$ Hi! Perhaps, you would find someone with a better answer than ours at cs.SE, the Computer Science portal, here at SE. :-) $\endgroup$ – Filippo De Bortoli May 15 '17 at 9:36
  • $\begingroup$ I don't fully understand what you mean by "backwards". What exactly is "backwards" here? Djikstras gives you the shortest path from a single point to all other points (single-source shortest path) $\endgroup$ – Siddharth Bhat May 15 '17 at 9:40
  • $\begingroup$ This is the problem, I have an algoritm- called the backward algorithm, but I don't know the proper name of it. It works similar to Dijkstra's, though it does not keep track of how many unchecked vertices remain, it just keep checking neighbouring vertices for distance- if it is a shorter distance to via some other the algorithm updates and move on. the distance $d(n):=min(d(n),d(w)+length(w,n))$ $\endgroup$ – S.n May 15 '17 at 10:04
  • 1
    $\begingroup$ Can it be called "Breadth first algorithm"? $\endgroup$ – S.n May 15 '17 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.