Peso mínimo da aresta ao longo de um caminho

Question

Como eu encontraria o máximo de um conjunto de pesos mínimos de aresta ao longo de todos os caminhos possíveis entre vértices arbitrários (u,v)?

Eu estava pensando em uma modificação do Floyd-Warshall?

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

O peso mínimo da borda é 1

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

O peso mínimo da borda é 3

Assim o resultado é max(1, 3) = 3

Answer 1

Sim, uma modificação do Floyd-Warshall funcionaria - em vez do comprimento do caminho mais curto, você acompanhará a "largura" máxima do caminho.

Se você estiver interessado apenas em dois vértices, poderá adotar uma abordagem mais simples:comece com um gráfico vazio e adicione arestas ordenadas por seu peso (de cima para baixo).Quando os nós em questão são conectados, a última aresta adicionada fornece a "largura" máxima.Feito corretamente (ou seja,usando conjunto disjunto para verificar a conexão), isso será mais rápido que o Floyd-Warshall.

Observação:Estou considerando apenas pesos positivos.