Suponha que você tenha um gráfico direcionado com comprimentos inteiros não negativos da borda que estão no intervalo de 0 a U - 1, inclusive. Qual é o algoritmo mais rápido para calcular uma árvore de abrangência mínima deste gráfico? Ainda podemos usar os algoritmos mínimos de spanning tree existentes, como o algoritmo de Kruskal O (m log n)) ou o algoritmo de Prim (O (m + n log n)). No entanto, nos casos em que U é pequeno, acho que deve ser possível fazer muito melhor iss

Existem algoritmos que são competitivos com os algoritmos MST mais tradicionais, capazes de explorar o fato de que os comprimentos das bordas estão limitados a estar em algum interval

Obrigado