Coursify

Greedy vs Non-Greedy: Which Standard Shortest-Path/MST Algorithms Are Not Greedy?

Greedy vs Non-Greedy: Which Standard Shortest-Path/MST Algorithms Are Not Greedy?

Verified Sources
Nov 1, 2026

In this question you’re asked to identify which algorithm among:

  • (i) Dijkstra’s shortest path algorithm
  • (ii) Kruskal algorithm
  • (iii) Bellman ford shortest path algorithm
  • (iv) Prim’s algorithm

is not a greedy algorithm.

A greedy algorithm makes an irrevocable locally optimal choice at each step. For shortest paths, Dijkstra is described as greedily selecting the closest unvisited vertex; for MST, Kruskal and Prim are greedy edge-selection methods based on the cut property. 3

By contrast, Bellman–Ford does not finalize vertices by a greedy “closest next” rule; instead it repeatedly performs relaxation over all edges for ∣V∣−1|V|-1 iterations, which is systematic and not “choose next locally best frontier item and lock it forever.” 2

Answer: (iii) Bellman-Ford algorithm.

Footnotes

  1. Dijkstra's algorithm - Wikipedia - Describes Dijkstra as extracting the minimum-distance unvisited vertex and relaxing edges. ↩

  2. Lecture 2 2.1 Greedy Algorithms 2.2 Minimum Spanning Trees (Harvard CS125) - Shows Kruskal pseudocode and explains correctness via cut property (safe greedy edge choice). ↩

  3. Minimum Spanning Trees (Princeton ALGS4) - States cut property as the basis for greedy MST algorithms; also contextualizes greedy construction. ↩

  4. Bellman–Ford algorithm - Wikipedia - Contrasts Dijkstra’s greedy selection with Bellman–Ford relaxing all edges ∣V∣−1|V|-1 times. ↩

  5. Bellman-Ford Algorithm | DSA | AlgoMaster.io - Explains Bellman–Ford relaxing every edge V−1V-1 times and contrasts with Dijkstra’s greedy locking behavior. ↩

Dijkstra vs Bellman-Ford (Shortest Path) — Greedy vs Relaxation Iterations

Key definitions (to classify algorithms correctly)

When classifying “greedy or not,” focus on whether the algorithm:

  1. Selects a locally optimal next choice (e.g., closest vertex / lightest safe edge),
  2. Does not revisit that choice’s consequences in the same way a greedy algorithm “locks in” decisions.

Important terms:

  • greedy algorithm
  • relaxation
  • shortest path
  • minimum spanning tree (MST)
  • cut property

Classify each option as greedy or not

  1. 1
    Step 1

    Dijkstra repeatedly picks the unvisited vertex with the lowest tentative distance and then relaxes outgoing edges from it—this corresponds to a greedy selection rule described as choosing the closest unvisited vertex.

  2. 2
    Step 2

    Kruskal sorts edges and adds the next lightest edge that doesn’t create a cycle; its correctness is tied to MST cut properties, which is the hallmark of greedy MST edge selection.

  3. 3
    Step 3

    Bellman–Ford relaxes all edges repeatedly for ∣V∣−1|V|-1 iterations, updating distances via relaxation until they converge; it is contrasted with Dijkstra’s greedy closest-vertex selection.

  4. 4
    Step 4

    Prim maintains a growing tree and repeatedly selects the minimum-weight edge that connects the tree to a new vertex; this is a greedy construction for MST.

Greedy “signature” vs algorithm

How directly each algorithm uses a locally optimal locked-in choice.

Why Bellman–Ford is the exception

Pro Tip

"When a shortest-path algorithm finalizes vertices in increasing tentative distance using a priority queue, it’s typically greedy (Dijkstra). When it repeatedly relaxes all edges ∣V∣−1|V|-1 times, it’s typically not greedy (Bellman–Ford)." 2

Footnotes

  1. Dijkstra's algorithm - Wikipedia - Describes Dijkstra as extracting the minimum-distance unvisited vertex and relaxing edges. ↩

  2. Bellman–Ford algorithm - Wikipedia - Contrasts Dijkstra’s greedy selection with Bellman–Ford relaxing all edges ∣V∣−1|V|-1 times. ↩

Common confusion: 'relaxation' does not automatically mean greedy

"Relaxation appears in both Dijkstra and Bellman–Ford, but they differ in how relaxation is scheduled: Dijkstra’s next choice is the closest unvisited vertex, while Bellman–Ford relaxes edges globally for ∣V∣−1|V|-1 rounds." 2

Footnotes

  1. Dijkstra's algorithm - Wikipedia - Describes Dijkstra as extracting the minimum-distance unvisited vertex and relaxing edges. ↩

  2. Bellman-Ford Algorithm | DSA | AlgoMaster.io - Explains Bellman–Ford relaxing every edge V−1V-1 times and contrasts with Dijkstra’s greedy locking behavior. ↩

Final selection

  • (i) Dijkstra’s algorithm: greedy (closest unvisited vertex selection)
  • (ii) Kruskal algorithm: greedy MST edge selection via cut property
  • (iii) Bellman–Ford algorithm: not greedy (relax all edges for ∣V∣−1|V|-1 iterations) 2
  • (iv) Prim’s algorithm: greedy MST construction

✅ Therefore, the algorithm that is not greedy is: (iii) Bellman–Ford.

Footnotes

  1. Dijkstra's algorithm - Wikipedia - Describes Dijkstra as extracting the minimum-distance unvisited vertex and relaxing edges. ↩

  2. Lecture 2 2.1 Greedy Algorithms 2.2 Minimum Spanning Trees (Harvard CS125) - Shows Kruskal pseudocode and explains correctness via cut property (safe greedy edge choice). ↩

  3. Bellman–Ford algorithm - Wikipedia - Contrasts Dijkstra’s greedy selection with Bellman–Ford relaxing all edges ∣V∣−1|V|-1 times. ↩

  4. Bellman-Ford Algorithm | DSA | AlgoMaster.io - Explains Bellman–Ford relaxing every edge V−1V-1 times and contrasts with Dijkstra’s greedy locking behavior. ↩

  5. Minimum Spanning Trees (Princeton ALGS4) - States cut property as the basis for greedy MST algorithms; also contextualizes greedy construction. ↩

Knowledge Check

Question 1 of 4
Q1Single choice

Which one of the following standard algorithms is NOT greedy?

Explore Related Topics

1

Optimal Approach for the 0/1 Knapsack Problem

2

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest‑path distances from a single source to all reachable vertices in a weighted graph whose edge weights are non‑negative, using a greedy selection of the minimum‑distance unsettled vertex and edge relaxation.

  • Keeps a tentative distance array and a min‑priority queue; extracting the smallest distance finalizes that vertex’s shortest path.
  • Correct only for non‑negative edges; negative weights invalidate the greedy invariant.
  • With an adjacency‑list and binary heap the time is O((V+E) log V); matrix scans give O(V²) and Fibonacci heaps can achieve O(E + V log V).
  • Storing a predecessor array allows reconstruction of actual shortest paths and early termination when a specific target is settled.
  • Fundamental in routing, navigation, and as a subroutine in many larger graph algorithms.
3

Shortest-Path Algorithms for a City Road Network

A city road network is modeled as a graph, and the appropriate single‑source shortest‑path algorithm depends on the edge‑weight properties.

  • All edges equal → use BFS, which finds minimum‑edge paths in O(∣V∣+∣E∣)O(|V|+|E|) time.
  • Non‑negative varying weights → use Dijkstra’s algorithm, greedy with a min‑priority queue, running in O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log|V|).
  • Some negative weights → use Bellman–Ford, relaxing all edges ∣V∣−1|V|-1 times (O(∣V∣∣E∣)O(|V||E|)) and detecting negative cycles.
  • The selection rule:
    Algorithm={BFSif all w(e) equalDijkstraif w(e)≥0Bellman-Fordif any w(e)<0\text{Algorithm}=\begin{cases}\text{BFS} & \text{if all }w(e)\text{ equal}\\ \text{Dijkstra} & \text{if }w(e)\ge0\\ \text{Bellman-Ford} & \text{if any }w(e)<0\end{cases}
  • A reachable negative cycle means no finite shortest path exists.
Browse all research articles