貪欲法
いくつかのアルゴリズムは貪欲法を基本戦略としているものの、厳密解が求まることが証明されている。
ダイクストラ法
プリム法
クラスカル法
最適化問題で厳密解となるには、動的計画法同様、部分構造最適性(英: optimal substructure)、つまり、部分問題を解き、それを利用して最適化問題の厳密解が解けることが必要である。