В чем разница между минимальным связующим деревом (MST) и кратчайшим путем для всех пар (APSP)?

Question

В чем разница между минимальным остовным деревом (MST) и кратчайшим путем для всех пар (APSP)? Также существует ли какая-нибудь проблема в реальном мире, при которой разница между ними четко видна?

Answer 1

Минимальное остовное дерево (MST) - это дерево, которое соединяет все узлы графа с наименьшей суммой весов ребер. Кратчайший путь между двумя узлами не обязательно должен проходить через края MST. Например, на этом графике:

   4
A ——— B
 \   /
3 \ / 3
   C

MST будет ребрами A C и B C, но кратчайший путь от A до B - это просто ребро AB.