2
$\begingroup$

I'm preparing some material for students about greedy algorithms, and there is one point that confuses me: how Dijkstra's algorithm fits into the greedy framework.

I would like to say that we have some optimization problem $\min_{S \in D} f(S)$. E.g.:

  • For MST, $S$ is a spanning tree and $f(S) = \sum_{e \in S} w(e)$
  • For the shortest path problem, $S$ is a path $s \to \ldots \to t$ and $f(S) = \sum_{e \in S} w(e)$

Now, I want to say that we construct $S$ one element at a time, selecting the "best" "available" element at every step. E.g. for MST, we select the shortest edge which doesn't create a cycle.

This approach doesn't seem to work for Dijkstra: we don't construct a path to $t$ one element at a time. For a lot of Dikstra's iterations, we process elements that are not on the shortest path. Exactly which nodes should be used for the shortest path, we'll know only when we reach $t$.

I do see a way to argue that Dijkstra is a greedy algorithm: instead of the shortest path problem, we should consider the all shortest path problem: finding shortest paths from $s$ to all vertices. However, in this case, the objective function $f$ is not clear: we have $|V|$ objectives (one for each vertex), not a single objective (for this problem, we can consider a sum of these functions, but this will only confuse the students). Since we don't have a single objective, an explanation of what we mean by "locally optimal" choice also becomes complicated.

So, what's my problem? Did I narrow the greedy algorithms too much by considering only optimization problems? In this case, what is a proper framework? Or is Dijkstra not a greedy algorithm?

$\endgroup$
1
  • $\begingroup$ Instead of asking whether Dijkstra's algorithm is a greedy algorithm, it is probably a requirement of a framework of greedy algorithms to illustrate Dijkstra's algorithm as an example. $\endgroup$
    – John L.
    Commented Sep 29, 2022 at 21:57

1 Answer 1

2
$\begingroup$

Yes, instead of the shortest path problem, we should consider the all shortest path problem or, more precisely, single-source shortest-paths (SSSP) problem. For SSSP, given node $s$, the objectives are $\min_{S_v} f(S_v)$ for all $v\in V$, where $S_v$ is a path $s \to \ldots \to v$ and $f(S_v) = \sum_{e \in S_v} w(e)$.

That must be a correct approach to introduce Dijkstra's algorithm since finding all shortest paths from one source could have been the given problem. You would not even have a choice then.

A basic idea illustrated by Dijkstra's algorithm is it is often easier to solve many related problems together instead of solving one isolated problem. It is of great educational value to instill and emphasize that idea early on.

Once we have a bunch of related problems, the next natural step is to find which one of them might be the easiest to attack. Or what is the easiest computation that can be done to solve one of those problems.

In the case of SSSP, the node that is nearest to the source can be computed easily. Knowing the source and that node, can we compute "next shortest path"? And so on to extend the frontier of our knowledge (pun intended). That seems the natural way to introduce Dijkstra's algorithm.

We can say that we will construct $S_v$'s that reach the respective objectives one edge at a time, selecting the "best" "available" element at every step, i.e., selecting the "unsettled" node that is "nearest" to the source at every step. So, the algorithm is greedy. A twist here is that we will end up with a different destination node $v$ at each step. It happens that the algorithm will find the optimal solutions to all objectives, producing a shortest-path tree.

Explaining a greedy algorithm using a single quantitative object to newcomers is a laudable idea. It might not be the best approach for this case, though.

$\endgroup$
3
  • $\begingroup$ In other words, Dijkstra's algorithm constructs the shortest path tree, and each step is greedily adding a leaf vertex with the minimum resulting tree height (longest path length). $\endgroup$
    – pcpthm
    Commented Oct 1, 2022 at 9:20
  • $\begingroup$ I think the term single-source shortest paths (SSSP) is more popular than all shortest path problem. $\endgroup$
    – pcpthm
    Commented Oct 1, 2022 at 9:22
  • $\begingroup$ @pcpthm Thanks for your feedback. I just updated my answer accordingly. $\endgroup$
    – John L.
    Commented Oct 1, 2022 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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