Дан граф с n вершинами, непрямой, взвешенный, без отрицательных циклов и двумя узлами s,t — найти путь из s в t, в котором самое тяжелое ребро на пути имеет наименьший вес между всеми путями из s в t.
одно решение, о котором я подумал, запустить BFS из s, найти какой-то путь между s и t, сохранить самое тяжелое ребро в пути, удалить его и сделать это не более чем |E| раз. сложность O(|V| + |E|)*E). Я ищу другое решение, которое может включать сетевой поток.
Спасибо.
