Confused about Dijkstras shortest path and MST

Question

Is Dijkstra's shortest path algorithm supposed to return a tree like it does in my textbook intro to algorithms? In examples I see online, it just shows the shortest path between 2 vertices. In my textbook it returns a tree with edges connected to every vertex. Im confused.

Answer 1

It depends on the textbook you're using: Dijkstra's algorithm solves the single source shortest path problem, and storing the predecessor of each vertex in a shortest path is not a lot of additional work if you're computing those paths or their lengths anyway. So depending on the sources and the applications, you may read something like:

• DijkstraParents(G, s), which returns the parent of each vertex in a shortest path from s to any other vertex in graph G;
• DijkstraTree(G, s), which can use the result of DijkstraParents(G, s) to return the actual shortest path tree;
• DijkstraPath(G, s, t), which can use the result of DijkstraParents(G, s) or DijkstraTree(G, s) to explicitly return a shortest path from s to t;
• ... and so on, including the computation of mere path lengths using the above.

In the end, all these versions are minor variations on the main algorithm, so use whichever one suits your needs.