全域木
ある頂点から他の頂点への移動コストが最小になるような経路を求める問題を最短経路問題という。ある頂点から他の全ての頂点に移動するコストが最小になる木のことを最短経路木といい、これは全域木である。最短経路問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法やベルマン-フォード法などが、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。