In Dijkstra algorithm, it takes the source, what about the sink?

Question

I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex? How can it work?

Thanks a lot.

Answer 1

Dijkstra's algorithm comes in two flavors: For computing the shortest path

• ... between a given source vertex and a given destination vertex or
• ... between a given source vertex and all other vertices

The difference can basically be summarized as whether it stops when the destination vertex is reached, or whether it processes the whole graph.

Your book obviously refers to the second one: It computes the shortest paths between the source vertex and all other vertices.

Answer 2

The Dijkstra's algorithm finds the shortest paths from a single vertex to all other vertices. It is an algorithm based on dynamic programming and its output is an array - where the i^th element of the array is the length of the shortest path from the source vertex to the vertex i.

During the work of the algorithm each vertex has a mark showing whether the shortest path length calculated so far for that vertex is final or not. You can modify the Dijsktra's algorithm by stopping it when the mark of the desired vertex is final.